共查询到20条相似文献,搜索用时 15 毫秒
1.
Ning An Sudhanva Gurumurthi Anand Sivasubramaniam Narayanan Vijaykrishnan Mahmut Kandemir Mary Jane Irwin 《The VLDB Journal The International Journal on Very Large Data Bases》2002,11(3):179-197
The proliferation of mobile and pervasive computing devices has brought energy constraints into the limelight. Energy-conscious
design is important at all levels of system architecture, and the software has a key role to play in conserving battery energy
on these devices. With the increasing popularity of spatial database applications, and their anticipated deployment on mobile
devices (such as road atlases and GPS-based applications), it is critical to examine the energy implications of spatial data
storage and access methods for memory resident datasets. While there has been extensive prior research on spatial access methods
on resource-rich environments, this is, perhaps, the first study to examine their suitability for resource-constrained environments.
Using a detailed cycle-accurate energy estimation framework and four different datasets, this paper examines the pros and
cons of three previously proposed spatial indexing alternatives from both the energy and performance angles. Specifically,
the Quadtree, Packed R-tree, and Buddy-Tree structures are evaluated and compared with a brute-force approach that does not
use an index. The results show that there are both performance and energy trade-offs between the indexing schemes for the
different queries. The nature of the query also plays an important role in determining the energy-performance trade-offs.
Further, technological trends and architectural enhancements are influencing factors on the relative behavior of the index
structures. The work in the query has a bearing on how and where (on a mobile client or/and on a server) it should be performed
for performance and energy savings. The results from this study will be beneficial for the design and implementation of embedded
spatial databases, accelerating their deployment on numerous mobile devices.
Received: November 11, 2001 / Accepted: March 12, 2002 Published online: November 14, 2002
This paper is a significantly extended version of preliminary work that appeared in the Proceedings of the Very Large Databases
(VLDB) 2001 Conference. The extensions include (i) a comparison of indexing alternatives carrying out the operations in a
brute-force manner; (ii) observations showing that datasets do play a role in power consumption; (iii) architectural solutions
to address the cache and memory hotspots for energy; and (iv) benefits when off-loading the work to a server over a wireless
medium compared to doing everything on the handheld device. 相似文献
2.
Effective timestamping in databases 总被引:3,自引:0,他引:3
Kristian Torp Christian S. Jensen Richard T. Snodgrass 《The VLDB Journal The International Journal on Very Large Data Bases》2000,8(3-4):267-288
Many existing database applications place various timestamps on their data, rendering temporal values such as dates and times
prevalent in database tables. During the past two decades, several dozen temporal data models have appeared, all with timestamps
being integral components. The models have used timestamps for encoding two specific temporal aspects of database facts, namely
transaction time, when the facts are current in the database, and valid time, when the facts are true in the modeled reality.
However, with few exceptions, the assignment of timestamp values has been considered only in the context of individual modification
statements.
This paper takes the next logical step: It considers the use of timestamping for capturing transaction and valid time in the
context of transactions. The paper initially identifies and analyzes several problems with straightforward timestamping, then
proceeds to propose a variety of techniques aimed at solving these problems. Timestamping the results of a transaction with
the commit time of the transaction is a promising approach. The paper studies how this timestamping may be done using a spectrum
of techniques. While many database facts are valid until now, the current time, this value is absent from the existing temporal types. Techniques that address this problem using different
substitute values are presented. Using a stratum architecture, the performance of the different proposed techniques are studied.
Although querying and modifying time-varying data is accompanied by a number of subtle problems, we present a comprehensive
approach that provides application programmers with simple, consistent, and efficient support for modifying bitemporal databases
in the context of user transactions.
Received: March 11, 1998 / Accepted July 27, 1999 相似文献
3.
A complete temporal relational algebra 总被引:5,自引:0,他引:5
Debabrata Dey Terence M. Barron Veda C. Storey 《The VLDB Journal The International Journal on Very Large Data Bases》1996,5(3):167-180
Various temporal extensions to the relational
model have been proposed. All
of these, however, deviate significantly from the original relational model.
This paper presents a temporal extension of the relational algebra that
is not significantly different from the original relational model, yet is
at least as expressive as any of the previous approaches. This algebra
employs multidimensional tuple time-stamping to capture the complete
temporal behavior of data. The basic relational operations are redefined as
consistent extensions of the existing operations in a manner that preserves
the basic algebraic equivalences of the snapshot (i.e., conventional static)
algebra. A new operation, namely temporal projection,
is introduced.
The complete update semantics are formally specified and aggregate functions
are defined. The algebra is closed, and reduces to the snapshot algebra. It
is also shown to be at least as expressive as the calculus-based temporal
query language TQuel. In order to assess the algebra, it is evaluated using
a set of twenty-six criteria proposed in the literature, and compared to
existing temporal relational algebras. The proposed algebra appears to
satisfy more criteria than any other
existing algebra.
Edited by
Wesley Chu. Received February 1993 / Accepted April
1995 相似文献
4.
Changzhou Wang X. Sean Wang 《The VLDB Journal The International Journal on Very Large Data Bases》2001,9(4):344-361
Similarity queries on complex objects are usually translated into searches among their feature vectors. This paper studies
indexing techniques for very high-dimensional (e.g., in hundreds) vectors that are sparse or quasi-sparse, i.e., vectors each having only a small number (e.g., ten) of non-zero or significant values. Based on the R-tree, the paper introduces the xS-tree
that uses lossy compression of bounding regions to guarantee a reasonable minimum fan-out within the allocated storage space
for each node. In addition, the paper studies the performance and scalability of the xS-tree via experiments.
Received: 3 May 1999 / Accepted: 23 October 2000 Published online: 27 April 2001 相似文献
5.
Abstract. The paper proposes a new method for efficient triangulation of large, unordered sets of 3D points using a CAD model comprising
NURBS entities. It is primarily aimed at engineering applications involving analysis and visualisation of measured data, such
as inspection, where a model of the object in question is available. Registration of the data to the model is the necessary
first step, enabling the triangulation to be efficiently performed in 2D, on the projections of the measured points onto the
model entities. The derived connectivity is then applied to the original 3D data. Improvement of the generated 3D mesh is
often necessary, involving mesh smoothing, constraint-based elimination of redundant triangles and merging of mesh patches.
Examples involving random measurements on aerospace and automotive free-form components are presented.
Received: 30 August 1999 / Accepted: 10 January 2000 相似文献
6.
In this paper, we present a novel approach for multimedia data indexing and retrieval that is machine independent and highly
flexible for sharing multimedia data across applications. Traditional multimedia data indexing and retrieval problems have
been attacked using the central data server as the main focus, and most of the indexing and query-processing for retrieval
are highly application dependent. This precludes the use of created indices and query processing mechanisms for multimedia
data which, in general, have a wide variety of uses across applications. The approach proposed in this paper addresses three
issues: 1. multimedia data indexing; 2. inference or query processing; and 3. combining indices and inference or query mechanism
with the data to facilitate machine independence in retrieval and query processing. We emphasize the third issue, as typically
multimedia data are huge in size and requires intra-data indexing. We describe how the proposed approach addresses various
problems faced by the application developers in indexing and retrieval of multimedia data. Finally, we present two applications
developed based on the proposed approach: video indexing; and video content authorization for presentation. 相似文献
7.
Yasushi Sakurai Masatoshi Yoshikawa Shunsuke Uemura Haruhiko Kojima 《The VLDB Journal The International Journal on Very Large Data Bases》2002,11(2):93-108
We propose a novel index structure, the A-tree (approximation tree), for similarity searches in high-dimensional data. The
basic idea of the A-tree is the introduction of virtual bounding rectangles (VBRs) which contain and approximate MBRs or data
objects. VBRs can be represented quite compactly and thus affect the tree configuration both quantitatively and qualitatively.
First, since tree nodes can contain a large number of VBR entries, fanout becomes large, which increases search speed. More
importantly, we have a free hand in arranging MBRs and VBRs in the tree nodes. Each A-tree node contains an MBR and its children
VBRs. Therefore, by fetching an A-tree node, we can obtain information on the exact position of a parent MBR and the approximate
position of its children. We have performed experiments using both synthetic and real data sets. For the real data sets, the
A-tree outperforms the SR-tree and the VA-file in all dimensionalities up to 64 dimensions, which is the highest dimension
in our experiments. Additionally, we propose a cost model for the A-tree. We verify the validity of the cost model for synthetic
and real data sets.
Edited by T. Sellis. Received: December 8, 2000 / Accepted: March 20, 2002 Published online: September 25, 2002 相似文献
8.
We present the Finite-Window Robust Sequential Estimator for the detection and analysis of corrosion in range images of gas
pipelines. This statistically robust, real-time technique estimates the pipeline surface range function in the presence of
noise, surface deviations, and changes in the underlying model. Deviations from the robust surface fit, corresponding to statistical
outliers, represent potential areas of corrosion. Because the algorithm estimates surface parameters over a finite, sliding
window of data, it can track moderately high-order surfaces using lower order models. The system is consistent, objective,
and non-destructive and can be used with the pipeline in service.
Received: 7 September 1999 / Accepted: 2 November 2000 相似文献
9.
Efficient similarity search for market basket data 总被引:2,自引:0,他引:2
Alexandros Nanopoulos Yannis Manolopoulos 《The VLDB Journal The International Journal on Very Large Data Bases》2002,11(2):138-152
Several organizations have developed very large market basket databases for the maintenance of customer transactions. New
applications, e.g., Web recommendation systems, present the requirement for processing similarity queries in market basket
databases. In this paper, we propose a novel scheme for similarity search queries in basket data. We develop a new representation
method, which, in contrast to existing approaches, is proven to provide correct results. New algorithms are proposed for the
processing of similarity queries. Extensive experimental results, for a variety of factors, illustrate the superiority of
the proposed scheme over the state-of-the-art method.
Edited by R. Ng. Received: August 6, 2001 / Accepted: May 21, 2002 Published online: September 25, 2002 相似文献
10.
David Gibson Jon Kleinberg Prabhakar Raghavan 《The VLDB Journal The International Journal on Very Large Data Bases》2000,8(3-4):222-236
We describe a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical
data. By “categorical data,” we mean tables with fields that cannot be naturally ordered by a metric – e.g., the names of
producers of automobiles, or the names of products offered by a manufacturer. Our approach is based on an iterative method
for assigning and propagating weights on the categorical values in a table; this facilitates a type of similarity measure
arising from the co-occurrence of values in the dataset. Our techniques can be studied analytically in terms of certain types
of non-linear dynamical systems.
Received February 15, 1999 / Accepted August 15, 1999 相似文献
11.
Bruno Becker Stephan Gschwind Thomas Ohler Bernhard Seeger Peter Widmayer 《The VLDB Journal The International Journal on Very Large Data Bases》1996,5(4):264-275
In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying
these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree
that supports insertions and deletions of data items at the current version and range queries and exact match queries for
any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds
are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming
a (single-version) B-tree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access
structures with certain properties directly, and it can be modified for others. 相似文献
12.
Comparing images using joint histograms 总被引:11,自引:0,他引:11
Color histograms are widely used for content-based image retrieval due to their efficiency and robustness. However, a color
histogram only records an image's overall color composition, so images with very different appearances can have similar color
histograms. This problem is especially critical in large image databases, where many images have similar color histograms.
In this paper, we propose an alternative to color histograms called a joint histogram, which incorporates additional information without sacrificing the robustness of color histograms. We create a joint histogram
by selecting a set of local pixel features and constructing a multidimensional histogram. Each entry in a joint histogram
contains the number of pixels in the image that are described by a particular combination of feature values. We describe a
number of different joint histograms, and evaluate their performance for image retrieval on a database with over 210,000 images.
On our benchmarks, joint histograms outperform color histograms by an order of magnitude. 相似文献
13.
Sibel Adalı K. Selçuk Candan Su-Shing Chen Kutluhan Erol V.S. Subrahmanian 《Multimedia Systems》1996,4(4):172-186
We describe how video data can be organized and structured so as to facilitate efficient querying. We develop a formal model
for video data and show how spatial data structures, suitably modified, provide an elegant way of storing such data. We develop
algorithms to process various kinds of video queries and show that, in most cases, the complexity of these algorithms is linear.
A prototype system, called the Advanced Video Information System (AVIS), based on these concepts, has been designed at the
University of Maryland. 相似文献
14.
UnQL: a query language and algebra for semistructured data based on structural recursion 总被引:5,自引:0,他引:5
Peter Buneman Mary Fernandez Dan Suciu 《The VLDB Journal The International Journal on Very Large Data Bases》2000,9(1):76-110
Abstract. This paper presents structural recursion as the basis of the syntax and semantics of query languages for semistructured data
and XML. We describe a simple and powerful query language based on pattern matching and show that it can be expressed using
structural recursion, which is introduced as a top-down, recursive function, similar to the way XSL is defined on XML trees.
On cyclic data, structural recursion can be defined in two equivalent ways: as a recursive function which evaluates the data
top-down and remembers all its calls to avoid infinite loops, or as a bulk evaluation which processes the entire data in parallel
using only traditional relational algebra operators. The latter makes it possible for optimization techniques in relational
queries to be applied to structural recursion. We show that the composition of two structural recursion queries can be expressed
as a single such query, and this is used as the basis of an optimization method for mediator systems. Several other formal
properties are established: structural recursion can be expressed in first-order logic extended with transitive closure; its
data complexity is PTIME; and over relational data it is a conservative extension of the relational calculus. The underlying
data model is based on value equality, formally defined with bisimulation. Structural recursion is shown to be invariant with
respect to value equality.
Received: July 9, 1999 / Accepted: December 24, 1999 相似文献
15.
The GMAP: a versatile tool for physical data independence 总被引:1,自引:0,他引:1
Odysseas G. Tsatalos Marvin H. Solomon Yannis E. Ioannidis 《The VLDB Journal The International Journal on Very Large Data Bases》1996,5(2):101-118
Physical data independence is touted as a central feature of modern
database systems. It allows users to frame queries in terms of the logical
structure of the data, letting a query processor automatically translate
them into optimal plans that access physical storage structures. Both
relational and object-oriented systems, however, force users to frame their
queries in terms of a logical schema that is directly tied to physical
structures. We present an approach that eliminates this dependence. All
storage structures are defined in a declarative language based on
relational algebra as functions of a logical schema. We present an
algorithm, integrated with a conventional query optimizer, that translates
queries over this logical schema into plans that access the storage
structures. We also show how to compile update requests into plans that
update all relevant storage structures consistently and optimally.
Finally, we report on experiments with a prototype implementation of our
approach that demonstrate how it allows storage structures to be tuned to
the expected or observed workload to achieve significantly better
performance than is possible with conventional techniques.
Edited by
Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received
September 15, 1994 / Accepted September 1, 1995 相似文献
16.
Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales. In other words,
they exhibit a multi-scale character. A special numerical multilevel technique associated with a particular hierarchical data
structure is adaptive mesh refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due
to its popularity, many scientists are in need of interactive visualization tools for AMR data.
In this article, we present a 3D texture-based volume-rendering algorithm for AMR data that directly utilizes the hierarchical
structure. Thereby fast rendering performance is achieved even for high-resolution data sets. To avoid multiple rendering
of regions that are covered by grids of different levels of resolution, we propose a space partitioning scheme to decompose
the volume into axis-aligned regions of equal-sized cells. Furthermore the problems of interpolation artifacts, opacity corrections,
and texture memory limitations are addressed.
Published online: November 6, 2002
Correspondence to: R. K?hler 相似文献
17.
Extracting skeletal curves from 3D scattered data 总被引:8,自引:0,他引:8
18.
In video processing, a common first step is to segment the videos into physical units, generally called shots. A shot is a video segment that consists of one continuous action. In general, these physical units need to be clustered
to form more semantically significant units, such as scenes, sequences, programs, etc. This is the so-called story-based video
structuring. Automatic video structuring is of great importance for video browsing and retrieval. The shots or scenes are
usually described by one or several representative frames, called key-frames. Viewed from a higher level, key frames of some shots might be redundant in terms of semantics. In this paper, we propose
automatic solutions to the problems of: (i) video partitioning, (ii) key frame computing, (iii) key frame pruning. For the
first problem, an algorithm called “net comparison” is devised. It is accurate and fast because it uses both statistical and
spatial information in an image and does not have to process the entire image. For the last two problems, we develop an original
image similarity criterion, which considers both spatial layout and detail content in an image. For this purpose, coefficients
of wavelet decomposition are used to derive parameter vectors accounting for the above two aspects. The parameters exhibit
(quasi-) invariant properties, thus making the algorithm robust for many types of object/camera motions and scaling variances.
The novel “seek and spread” strategy used in key frame computing allows us to obtain a large representative range for the
key frames. Inter-shot redundancy of the key-frames is suppressed using the same image similarity measure. Experimental results
demonstrate the effectiveness and efficiency of our techniques. 相似文献
19.
Speeding up construction of PMR quadtree-based spatial indexes 总被引:5,自引:0,他引:5
Gisli R. Hjaltason Hanan Samet 《The VLDB Journal The International Journal on Very Large Data Bases》2002,11(2):109-137
Spatial indexes, such as those based on the quadtree, are important in spatial databases for efficient execution of queries
involving spatial constraints, especially when the queries involve spatial joins. In this paper we present a number of techniques
for speeding up the construction of quadtree-based spatial indexes, specifically the PMR quadtree, which can index arbitrary
spatial data. We assume a quadtree implementation using the “linear quadtree”, a disk-resident representation that stores
objects contained in the leaf nodes of the quadtree in a linear index (e.g., a B-tree) ordered based on a space-filling curve.
We present two complementary techniques: an improved insertion algorithm and a bulk-loading method. The bulk-loading method
can be extended to handle bulk-insertions into an existing PMR quadtree. We make some analytical observations about the I/O
cost and CPU cost of our PMR quadtree bulk-loading algorithm, and conduct an extensive empirical study of the techniques presented
in the paper. Our techniques are found to yield significant speedup compared to traditional quadtree building methods, even
when the size of a main memory buffer is very small compared to the size of the resulting quadtrees.
Edited by R. Sacks-Davis. Received: July 10, 2001 / Accepted: March 25, 2002 Published online: September 25, 2002 相似文献
20.
Approximate similarity retrieval with M-trees 总被引:4,自引:0,他引:4
Pavel Zezula Pasquale Savino Giuseppe Amato Fausto Rabitti 《The VLDB Journal The International Journal on Very Large Data Bases》1998,7(4):275-293
Motivated by the urgent need to improve the efficiency of similarity queries, approximate similarity retrieval is investigated
in the environment of a metric tree index called the M-tree. Three different approximation techniques are proposed, which
show how to forsake query precision for improved performance. Measures are defined that can quantify the improvements in performance
efficiency and the quality of approximations. The proposed approximation techniques are then tested on various synthetic and
real-life files. The evidence obtained from the experiments confirms our hypothesis that a high-quality approximated similarity
search can be performed at a much lower cost than that needed to obtain the exact results. The proposed approximation techniques
are scalable and appear to be independent of the metric used. Extensions of these techniques to the environments of other
similarity search indexes are also discussed.
Received July 7, 1998 / Accepted October 13, 1998 相似文献