NDLI: Making B+- trees cache conscious in main memory

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

Making B+- trees cache conscious in main memory

Content Provider	ACM Digital Library
Author	Rao, Jun Ross, Kenneth A.
Abstract	Previous research has shown that cache behavior is important for main memory index structures. Cache conscious index structures such as Cache Sensitive Search Trees (CSS-Trees) perform lookups much faster than binary search and T-Trees. However, CSS-Trees are designed for decision support workloads with relatively static data. Although $B^{+}-Trees$ are more cache conscious than binary search and T-Trees, their utilization of a cache line is low since half of the space is used to store child pointers. Nevertheless, for applications that require incremental updates, traditional $B^{+}-Trees$ perform well.Our goal is to make $B^{+}-Trees$ as cache conscious as CSS-Trees without increasing their update cost too much. We propose a new indexing technique called “Cache Sensitive $B^{+}-Trees”$ $(CSB^{+}-Trees).$ It is a variant of $B^{+}-Trees$ that stores all the child nodes of any given node contiguously, and keeps only the address of the first child in each node. The rest of the children can be found by adding an offset to that address. Since only one child pointer is stored explicitly, the utilization of a cache line is high. $CSB^{+}-Trees$ support incremental updates in a way similar to $B^{+}-Trees.We$ also introduce two variants of $CSB^{+}-Trees.$ Segmented $CSB^{+}-Trees$ divide the child nodes into segments. Nodes within the same segment are stored contiguously and only pointers to the beginning of each segment are stored explicitly in each node. Segmented $CSB^{+}-Trees$ can reduce the copying cost when there is a split since only one segment needs to be moved. Full $CSB^{+}-Trees$ preallocate space for the full node group and thus reduce the split cost. Our performance studies show that $CSB^{+}-Trees$ are useful for a wide range of applications.
Starting Page	475
Ending Page	486
Page Count	12
File Format	PDF
ISBN	1581132174
DOI	10.1145/342009.335449
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-05-16
Publisher Place	New York
Access Restriction	Subscribed
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