NDLI: Time-optimal ranking algorithms on sorted matrices

Content Provider	IEEE Xplore Digital Library
Author	Bokka, V. Gurla, H. Olariu, S. Schwing, J.L. Wilson, L.
Copyright Year	1995
Description	Author affiliation: Dept. of Comput. Sci., Old Dominion Univ., Norfolk, VA, USA (Bokka, V.; Gurla, H.; Olariu, S.; Schwing, J.L.; Wilson, L.)
Abstract	Answering rank queries is a recurring operation in various application domains including geographic data processing, information retrieval, database design, information management, and medical image processing. Many of these applications involve data stored in a matrix satisfying a number of properties. One property that occurs time and again in applications specifies that the rows and the columns of the matrix are independently sorted. It is customary to refer to such a matrix as sorted. An instance of the Batched Ranking problem, (BR, for short) involves a sorted matrix A of items from a totally ordered universe, along with a collection Q of queries of the following type: for a query q/sub j/ one is interested in the number of items in A that are smaller than q/sub j/. The BR problem asks for solving all queries in Q. In this work, we consider the BR problem in the following context: the matrix A is pretiled, one item per processor, onto an enhanced mesh of size /spl radic/n/spl times//spl radic/n; the m queries are stored, one per processor, in the first m//spl radic/n columns of the platform. Our main contribution is twofold. First, we show that any algorithm that solves the BR problem must take at least /spl Omega/(log n+/spl radic/m) time in the worst case. Second, we show that this time lower bound is tight on meshes of size /spl radic/n/spl times//spl radic/n enhanced with multiple broadcasting, by exhibiting an algorithm solving the BR problem in O(log n+/spl radic/m) time on such a platform.
Starting Page	42
Ending Page	53
File Size	797337
Page Count	12
File Format	PDF
ISBN	0818671092
ISSN	10636862
DOI	10.1109/ASAP.1995.522904
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1995-07-24
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Broadcasting Application software Data processing Computer architecture Information retrieval Image databases Biomedical image processing Computer science Image retrieval Health information management
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture

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

Image information systems

A general purpose architecture for image retrieval in databases

Using predeclaration for efficient read-only transaction processing in wireless data broadcast

Web image retrieval using majority-based ranking approach

A fault-tolerant approach to secure information retrieval

Leveraging community metadata for multimodal image ranking

Guaranteed, reliable, secure broadcast networks

Associative information processing: algorithms and system

Scheduling real-time data items in multiple channels and multiple receivers environments

Time-optimal ranking algorithms on sorted matrices

Similar Documents

Image information systems

A general purpose architecture for image retrieval in databases

Using predeclaration for efficient read-only transaction processing in wireless data broadcast

Web image retrieval using majority-based ranking approach

A fault-tolerant approach to secure information retrieval

Leveraging community metadata for multimodal image ranking

Guaranteed, reliable, secure broadcast networks

Associative information processing: algorithms and system

Scheduling real-time data items in multiple channels and multiple receivers environments

Time-optimal ranking algorithms on sorted matrices