NDLI: Incremental maintenance of length normalized indexes for approximate string matching

Please wait, while we are loading the content...

Authenticated join processing in outsourced databases

Dependency-aware reordering for parallelizing query optimization in multi-core CPUs

Efficiently incorporating user feedback into information extraction and integration programs

Attacks on privacy and deFinetti's theorem

A comparison of approaches to large-scale data analysis

Exploiting context analysis for combining multiple entity resolution systems

Generating example data for dataflow programs

Dictionary-based order-preserving string compression for main memory column stores

Optimizing complex extraction programs over evolving text data

Ranking distributed probabilistic data

Query simplification: graceful degradation for join-order optimization

E = $MC^{3}:$ managing uncertain enterprise data in a cluster-computing environment

Scalable skyline computation using object-based space partitioning

Quality and efficiency in high dimensional nearest neighbor search

Cost based plan selection for xpath

Top-k generation of integrated schemas based on directed and weighted correspondences

Keyword search in databases: the power of RDBMS

DDE: from dewey to a fully dynamic XML labeling scheme

Efficient approximate entity extraction with edit distance constraints

A revised r*-tree in comparison with related index structures

Data warehouse technology by infobright

Advances in flash memory SSD technology for enterprise database applications

A comparison of flexible schemas for software as a service

Partial join order optimization in the paraccel analytic database

Taming the storage dragon: the adventures of hoTMaN

Building community-centric information exploration applications on social content sites

Design for interaction

Storage class memory: technology, systems and applications

Large-scale uncertainty management systems: learning and exploiting your data

PRIMA: archiving and querying historical data with evolving schemas

Interactive anonymization of sensitive data

Exploring biomedical databases with BioNav

SmartCIS: integrating digital and physical environments

A common database approach for OLTP and OLAP using an in-memory column database

Privacy integrated queries: an extensible platform for privacy-preserving data analysis

Query processing techniques for solid state drives

Uncertainty management in rule-based information extraction systems

Secure kNN computation on encrypted databases

Asynchronous view maintenance for VLSD databases

Entity resolution with iterative blocking

A framework for testing query transformation rules

Self-organizing tuple reconstruction in column-stores

Robust web extraction: an approach based on a probabilistic tree-edit model

Top-k queries on uncertain data: on score distribution and typical answers

Robust and efficient algorithms for rank join evaluation

Indexing correlated probabilistic databases

Minimizing the communication cost for continuous skyline maintenance

Query by output

Continuous obstructed nearest neighbor queries in spatial databases

ROX: run-time optimization of XQueries

Core schema mappings

Efficient type-ahead search on relational data: a TASTIER approach

Simplifying XML schema: effortless handling of nondeterministic regular expressions

GAMPS: compressing multi sensor data by grouping and amplitude scaling

3-HOP: a high-compression indexing scheme for reachability query

Stream warehousing with DataDepot

Parallelizing extensible query optimizers

The design of the force.com multitenant internet application development platform

Dynamic plan generation for parameterized queries

Compensation-aware data types in RDBMS

QoX-driven ETL design: reducing the cost of ETL consulting engagements

Voyagers and voyeurs: supporting social data analysis

Distributed data-parallel computing using a high-level programming language

FPGA: what's in it for a database?

DejaVu: declarative pattern matching over live and archived streams of events

The perm provenance management system in action

MobileMiner: a real world case study of data mining in mobile communication

DataLens: making a good first impression

Transforming data access through public visualization

Secure outsourced aggregation via one-way chains

FlashLogging: exploiting flash devices for synchronous logging performance

Skip-and-prune: cosine-based top-k query processing for efficient context-sensitive document retrieval

Privacy preservation of aggregates in hidden databases: why and how?

ZStream: a cost-based query processor for adaptively detecting composite events

A grammar-based entity representation framework for data cleaning

Cross-tier, label-based security enforcement for web applications

An architecture for recycling intermediates in a column-store

Combining keyword search and forms for ad hoc querying of databases

Secondary-storage confidence computation for conjunctive queries with inequalities

Incremental maintenance of length normalized indexes for approximate string matching

Estimating the confidence of conditional functional dependencies

Kernel-based skyline cardinality estimation

Detecting and resolving unsound workflow views for correct provenance analysis

Monitoring path nearest neighbor in road networks

Scalable join processing on very large RDF graphs

A gauss function based approach for unbalanced ontology matching

Extending autocompletion to tolerate errors

FlexRecs: expressing and combining flexible recommendations

Optimizing i/o-intensive transactions in highly interactive applications

Serial and parallel methods for i/o efficient suffix tree construction

Peta-scale data warehousing at Yahoo!

A data warehouse appliance for the mass market

Filtered statistics

Ordering, distinctness, aggregation, partitioning and DQP optimization in sybase ASE 15

Access control in the aqualogic data services platform

Query optimizers: time to rethink the contract?

Augmented social cognition: using social web technology to enhance the ability of groups to remember, think, and reason

Keyword search on structured and semi-structured data

StreamShield: a stream-centric approach towards security and privacy in data stream environments

A decisions query language (DQL): high-level abstraction for mathematical programming over databases

Fast and dynamic OLAP exploration using UDFs

MEDIALIFE: from images to a life chronicle

Database research in computer games

Supporting a spectrum of out-of-order event processing technologies: from aggressive to conservative methodologies

FERRY: database-supported program execution

AIDE: ad-hoc intents detection engine over query logs

Enabling enterprise mashups over unstructured text feeds with InfoSphere MashupHub and SystemT

Anonymized data: generation, models, usage

ELMR: lightweight mobile health records

Extreme visualisation of query optimizer search space

Exploring schema repositories with schemr

Answering web queries using structured data sources

Bridging the application and DBMS divide using static analysis and dynamic profiling

MayBMS: a probabilistic database management system

Search your memory ! - an associative memory based desktop search system

HDSampler: revealing data behind web form interfaces

Interactive plan hints for query optimization

ORDEN: outlier region detection and exploration in sensor networks

ExQueX: exploring and querying XML documents

Hermes: a travel through semantics on the data web

What's on the grapevine?

CourseRank: a social system for course planning

Vispedia: on-demand data integration for interactive visualization and exploration

Incremental maintenance of length normalized indexes for approximate string matching

Content Provider	ACM Digital Library
Author	Hadjieleftheriou, Marios Koudas, Nick Srivastava, Divesh
Abstract	Approximate string matching is a problem that has received a lot of attention recently. Existing work on information retrieval has concentrated on a variety of similarity measures TF/IDF, BM25, HMM, etc.) specifically tailored for document retrieval purposes. As new applications that depend on retrieving short strings are becoming popular(e.g., local search engines like YellowPages.com, Yahoo!Local, and Google Maps) new indexing methods are needed, tailored for short strings. For that purpose, a number of indexing techniques and related algorithms have been proposed based on length normalized similarity measures. A common denominator of indexes for length normalized measures is that maintaining the underlying structures in the presence of incremental updates is inefficient, mainly due to data dependent, precomputed weights associated with each distinct token and string. Incorporating updates usually is accomplished by rebuilding the indexes at regular time intervals. In this paper we present a framework that advocates lazy update propagation with the following key feature: Efficient, incremental updates that immediately reflect the new data in the indexes in a way that gives strict guarantees on the quality of subsequent query answers. More specifically, our techniques guarantee against false negatives and limit the number of false positives produced. We implement a fully working prototype and illustrate that the proposed ideas work really well in practice for real datasets.
Starting Page	429
Ending Page	440
Page Count	12
File Format	PDF
ISBN	9781605585512
DOI	10.1145/1559845.1559891
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-06-29
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	String indexing Updates Idf Length normalization Inverted index
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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