Stanford InfoLab Publication Server

Proximity search in databases.

Goldman, R. and Shivakumar, N. and Venkatasubramanian, S. and Garcia-Molina, H. (1998) Proximity search in databases. In: 24rd International Conference on Very Large Data Bases (VLDB 1998), August 24-27, 1998, New York, NY.




An information retrieval (IR) engine can rank documents based on textual proximity of keywords within each document. In this paper we apply this notion to search across an entire database for objects that are "near" other relevant objects. Proximity search enables simple "focusing" queries based on general relationships among objects, helpful for interactive query sessions. We view the database as a graph, with data in vertices (objects) and relationships indicated by edges. Proximity is defined based on shortest paths between objects. We have implemented a prototype search engine that uses this model to enable keyword searches over databases, and we have found it very effective for quickly finding relevant information. Computing the distance between objects in a graph stored on disk can be very expensive. Hence, we show how to build compact indexes that allow us to quickly find the distance between objects at search time. Experiments show that our algorithms are effcient and scale well.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:Lore, graph databases, semistructured data, keyword search
Subjects:Computer Science > Semistructured Data
Related URLs:Project Homepage
ID Code:321
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:29 Dec 2008 09:38

Download statistics

Repository Staff Only: item control page