NDLI: The onion technique: indexing for linear optimization queries

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

Mining frequent patterns without candidate generation

Data mining on an OLTP system (nearly) for free

Turbo-charging vertical mining of large databases

High speed on-line backup when using logical log operations

Efficient resumption of interrupted warehouse loads

On-line reorganization in object databases

Finding generalized projected clusters in high dimensional spaces

Density biased sampling: an improved method for data mining and clustering

LOF: identifying density-based local outliers

Answering complex SQL queries using automatic summary tables

Synchronizing a database to improve freshness

How to roll a join: asynchronous incremental view maintenance

On wrapping query languages and efficient XML integration

XMill: an efficient compressor for XML data

XTRACT: a system for extracting document type descriptors from XML documents

Spatial join selectivity using power laws

Closest pair queries in spatial databases

Influence sets based on reverse nearest neighbor queries

MOCHA: a self-extensible database middleware system for distributed data sources

Towards self-tuning data placement in parallel database systems

LH*RS: a high-availability scalable distributed data structure using Reed Solomon Codes

Efficient and extensible algorithms for multi query optimization

Eddies: continuously adaptive query processing

A chase too far?

WSQ/DSQ: a practical approach for combined querying of databases and the Web

A framework for expressing and combining preferences

Microsoft TerraServer: a spatial data warehouse

A data model and data structures for moving objects databases

Indexing the positions of continuously moving objects

Adaptive multi-stage distance join processing

Finding replicated Web collections

WebView materialization

NiagaraCQ: a scalable continuous query system for Internet databases

The onion technique: indexing for linear optimization queries

On effective multi-dimensional indexing for strings

Efficient and cost-effective techniques for browsing and indexing large video databases

Efficient algorithms for mining outliers from large data sets

Privacy-preserving data mining

Designing and mining multi-terabyte astronomy archives: the Sloan Digital Sky Survey

Approximating multi-dimensional aggregate range queries over real attributes

Making B+- trees cache conscious in main memory

Congressional samples for approximate answering of group-by queries

Counting, enumerating, and sampling of execution plans in a cost-based query optimizer

Benchmarking queries over trees: learning the hard truth the hard way

Maintenance of cube automatic summary tables

Challenges in automating declarative business rules to enable rapid business response

Expressing business rules

Going beyond personalization: rule engines at work

DLFM: a transactional resource manager

Online index rebuild

Indexing images in Oracle8i

Handling very large databases with informix extended parallel server

Internet traffic warehouse

SQLEM: fast clustering in SQL using the EM algorithm

Anatomy of a real E-commerce system

From browsing to interacting: DBMS support for responsive websites

Index research (panel session): forest or trees?

Application architecture (panel session): 2Tier or 3Tier? What is DBMS's role?

Of XML and databases (panel session): where's the beef?

Designing an ultra highly available DBMS (tutorial session)

Data management in eCommerce (tutorial session): the good, the bad, and the ugly

Data access (tutorial session)

LDAP directory services- just another database application? (tutorial session)

Research issues in moving objects databases (tutorial session)

Self-organizing data sharing communities with SAGRES

λ-DB: an ODMG-based object-oriented DBMS

An approximate search engine for structural databases

SERFing the Web: web site management made easy

HOMER: a model-based CASE tool for data-intensive Web sites

FACT: a learning based Web query processing system

javax.XXL: a prototype for a library of query processing algorithms

i3: intelligent, interactive investigation of OLAP data cubes

AJAX: an extensible data cleaning tool

Concept based design of data warehouses: the DWQ demonstrators

Towards data mining benchmarking: a test bed for performance study of frequent pattern mining

Image mining in IRIS: integrated retinal information system

MOCHA: a database middleware system featuring automatic deployment of application-specific functionality

A goal-driven auto-configuration tool for the distributed workflow management system mentorlite

TIP: a temporal extension to Informix

AQR-toolkit: an adaptive query routing middleware for distributed data intensive systems

SPIRE: a progressive content-based spatial image retrieval engine

Integrating replacement policies in StorM: an extensible approach

DISIMA: a distributed and interoperable image database system

The MLPQ/GIS constraint database system

The onion technique: indexing for linear optimization queries

Content Provider	ACM Digital Library
Author	Lo, Ming-Ling Bergman, Lawrence Li, Chung-Sheng Castelli, Vittorio Chang, Yuan-Chi Smith, John R.
Abstract	This paper describes the Onion technique, a special indexing structure for linear optimization queries. Linear optimization queries ask for top-N records subject to the maximization or minimization of linearly weighted sum of record attribute values. Such query appears in many applications employing linear models and is an effective way to summarize representative cases, such as the top-50 ranked colleges. The Onion indexing is based on a geometric property of convex hull, which guarantees that the optimal value can always be found at one or more of its vertices. The Onion indexing makes use of this property to construct convex hulls in layers with outer layers enclosing inner layers geometrically. A data record is indexed by its layer number or equivalently its depth in the layered convex hull. Queries with linear weightings issued at run time are evaluated from the outmost layer inwards. We show experimentally that the Onion indexing achieves orders of magnitude speedup against sequential linear scan when N is small compared to the cardinality of the set. The Onion technique also enables progressive retrieval, which processes and returns ranked results in a progressive manner. Furthermore, the proposed indexing can be extended into a hierarchical organization of data to accommodate both global and local queries.
Starting Page	391
Ending Page	402
Page Count	12
File Format	PDF
ISBN	1581132174
DOI	10.1145/342009.335433
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-05-16
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Linear optimization Database indexing
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