BLINKS: Ranked Keyword Searches on Graphs

Summary: BLINKS: bi-level indexing for top-k keyword searches on graphs. Block-partitioned graphs with block-level summaries enable pruning and fast intra-block search; provable performance bounds and orders-of-magnitude speedups over prior approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3861
Venue: SIGMOD
Year: 2007
Pagerank: 0.00028343691
Overall Rank: 302 | 97.91%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 48 of 48 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
377	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025074538
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261
949	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.0001510288
1,000	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014714977
1,168	SODA: Generating SQL for Business Users	2012	VLDB	0.00013531301
1,502	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011614522
1,564	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00011340407
1,575	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00011288804
1,794	Summary Graphs for Relational Database Schemas	2011	VLDB	0.00010516799
2,017	DB&IR: Both Sides Now (Extended Abstract)	2007	SIGMOD	9.7875061e-05
2,127	EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data	2008	SIGMOD	9.4806381e-05
2,190	Keyword Search on External Memory Data Graphs	2008	VLDB	9.3356692e-05
2,557	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5484449e-05
2,774	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.140768e-05
2,990	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	7.7727915e-05
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05
3,439	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.0916563e-05
3,456	Keyword Search on Structured and Semi-Structured Data	2009	SIGMOD	7.0756309e-05
4,064	REX: Explaining Relationships between Entity Pairs	2012	VLDB	6.4763384e-05
4,097	Structured Annotations of Web Queries	2010	SIGMOD	6.4504937e-05
4,143	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.4096394e-05
4,410	Efficient Type-Ahead Search on Relational Data: a TASTIER Approach	2009	SIGMOD	6.2012075e-05
4,838	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB	5.883146e-05
5,031	Actively Soliciting Feedback for Query Answers in Keyword Search-Based Data Integration	2013	VLDB	5.7433161e-05
5,363	An In-Depth Benchmarking of Text-to-SQL Systems	2021	SIGMOD	5.5467941e-05
5,549	Query Biased Snippet Generation in XML Search	2008	SIGMOD	5.4440282e-05
5,697	Efficient and Progressive Group Steiner Tree Search	2016	SIGMOD	5.3672389e-05
5,933	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2620152e-05
6,208	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB	5.1511024e-05
6,360	DISKs: A System for Distributed Spatial Group Keyword Search on Road Networks	2012	VLDB	5.0909523e-05
6,574	Supporting Keyword Search in Product Database: A Probabilistic Approach	2013	VLDB	4.999847e-05
6,793	Automatically Incorporating New Sources in Keyword Search-Based Data Integration	2010	SIGMOD	4.9201319e-05
6,854	DBease: Making Databases User-friendly and Easily Accessible	2011	CIDR	4.901546e-05
7,271	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	4.7764555e-05
7,313	Nearest Keyword Search in XML Documents	2011	SIGMOD	4.7599924e-05
7,365	Sharing Work in Keyword Search over Databases	2011	SIGMOD	4.7459715e-05
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05
8,746	Full-Power Graph Querying: State of the Art and Challenges	2023	VLDB	4.4520434e-05
8,763	Toward Scalable Keyword Search over Relational Data	2010	VLDB	4.4520434e-05
9,057	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	4.3997447e-05
9,589	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD	4.3167828e-05
9,590	An Effective and Versatile Keyword Search Engine on Heterogenous Data Sources	2008	VLDB	4.3167828e-05
9,897	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	4.2559233e-05
11,900	Looking at Everything in Context	2015	CIDR	4.1905499e-05
12,098	Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data	2013	VLDB	4.1905499e-05
12,274	Ten Thousand SQLs: Parallel Keyword Queries Computing	2010	VLDB	4.1905499e-05
12,290	Searching Workflows with Hierarchical Views	2010	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
53	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00065993143
73	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.0005840064
186	Proximity Search in Databases	1998	VLDB	0.0003618341
278	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB	0.00029322862
320	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00027574254
337	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00027002505
436	XSEarch: A Semantic Search Engine for XML	2003	VLDB	0.00023264416
547	Schema-Free XQuery	2004	VLDB	0.00020372992
873	Effective Keyword Search in Relational Databases	2006	SIGMOD	0.0001570125
989	Efficient Keyword Search for Smallest LCAs in XML Databases	2005	SIGMOD	0.00014805498
1,072	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00014256848
1,409	Personal Information Management with Semex	2005	SIGMOD	0.00012153957
2,166	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD	9.3918483e-05
2,229	The SphereSearch Engine for Unified Ranked Retrieval of Heterogeneous XML and Web Documents	2005	VLDB	9.2422485e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,838	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB	5.883146e-05
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014759406
7,273	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.775366e-05
2,774	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.140768e-05
337	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00027002505
9,589	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD	4.3167828e-05
12,247	Exploratory Keyword Search on Data Graphs	2010	SIGMOD	4.1905499e-05
2,190	Keyword Search on External Memory Data Graphs	2008	VLDB	9.3356692e-05
1,453	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00011921738
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05