D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data

Summary: D(k)-index: adaptive, bisimilarity-based structural summary for graph data; generalizes 1-index and A(k)-index. It tunes the index to the current query workload for faster path queries and updates; experiments show improvement over static summaries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h5c9f2ddadccbb31d
Venue: SIGMOD
Year: 2003
Pagerank: 0.00012391703
Overall Rank: 1,027 | 93.12%
DOI: 10.1145/872757.872776

Incoming Non-self Citations Over Time

Authors

1. Qun Chen (National University of Singapore)
2. Andrew Lim (National University of Singapore)
3. Kian Win Ong (National University of Singapore)

BibTeX Citation

@inproceedings{chen_sigmod03,
        title = {{D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data}},
        author = {Chen, Qun and Lim, Andrew and Ong, Kian Win},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872776},
        url = {https://dl.acm.org/doi/10.1145/872757.872776},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026634326
333	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020712452
1,376	Query Preserving Graph Compression	2012	SIGMOD	0.00010857788
1,378	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00010848501
1,502	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010431532
2,387	Towards Graph Containment Search and Indexing	2007	VLDB	8.5236741e-05
4,219	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.7141046e-05
4,568	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.5171208e-05
5,247	Indexing Dataspaces	2007	SIGMOD	6.1985096e-05
5,574	Representing Paths in Graph Database Pattern Matching	2023	VLDB	6.0628579e-05
5,831	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD	5.9624819e-05
6,087	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB	5.8741996e-05
6,968	Indexing Temporal XML Documents	2004	VLDB	5.6158112e-05
7,441	Structured Materialized Views for XML Queries	2007	VLDB	5.5118606e-05
7,717	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.4545945e-05
8,586	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.2939333e-05
9,715	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	5.1236529e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00042977538
167	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027156235
352	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020179814
445	A Fast Index for Semistructured Data	2001	VLDB	0.0001815112
521	XQuery: A Query Language for XML	2003	SIGMOD	0.00016897042
744	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014275788
926	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00013025014
2,378	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.5315761e-05
3,195	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.530952e-05
3,497	Updates for Structure Indexes	2002	VLDB	7.2356454e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,162	DIDS: Double Indices and Double Summarizations for Fast Similarity Search	2024	VLDB
2	8,988	Dynamic Data Structures for Document Collections and Graphs	2015	PODS
3	12,636	Efficient Indexing for Diverse Query Results	2013	VLDB
4	7,309	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB
5	445	A Fast Index for Semistructured Data	2001	VLDB
6	12,146	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB
7	9,688	Indexing for Keyword Search with Structured Constraints	2023	PODS
8	176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
9	5,831	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD
10	3,497	Updates for Structure Indexes	2002	VLDB