NDLI: A New Indexing Method for Approximate Search in Text Databases

Content Provider	IEEE Xplore Digital Library
Author	Fei Shi Mefford, C.
Copyright Year	2005
Description	Author affiliation: Comput. Sci. Dept., Suffolk Univ., Boston, MA (Fei Shi; Mefford, C.)
Abstract	We present an index structure to support the approximate keyword search in text databases. In an approximate keyword search query, the user presents a query word Q and a tolerance value k (kges0), and wishes to find all documents in the database that contain the query word Q or any other word in the vocabulary that matches Q approximately (We say that two words match each other approximately if the edit distance between them does not exceed the tolerance value k. In a typical text database application, a user chooses k=1, 2, 3, or 4). Our index structure is built on the underlying vocabulary of the text database. The new technique has two principal components - a new data structure called the V-tree and its partition methods for clustering words in the vocabulary into subgroups. We have implemented our index structure and conducted experiments on real-world data. Our experiments show that even for very large text database, the construction of our index and a search for keywords that match the query word approximately can be done quickly. Our implementation makes it clear that the V-tree data structure can be easily integrated into existing access structures built on the database such as the inverted index file
Sponsorship	Univ. of Aizu, Japan Nat. Natural Sci. Found. China Fudan GrandHorizon Inf. Technol., Inc. China Hewlett-Packard Co., Ltd
Starting Page	70
Ending Page	76
File Size	225529
Page Count	7
File Format	PDF
ISBN	076952432X
DOI	10.1109/CIT.2005.23
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-09-21
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Proteins Vocabulary Dictionaries Sequences Keyword search Data structures Information retrieval Database systems Indexes Indexing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in