共查询到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.
Searching in metric spaces by spatial approximation 总被引:5,自引:0,他引:5
Gonzalo Navarro 《The VLDB Journal The International Journal on Very Large Data Bases》2002,11(1):28-46
We propose a new data structure to search in metric spaces. A metric space is formed by a collection of objects and a distance function defined among them which satisfies the triangle inequality. The goal is, given a set of objects and a query, retrieve those
objects close enough to the query. The complexity measure is the number of distances computed to achieve this goal. Our data
structure, called sa-tree (“spatial approximation tree”), is based on approaching the searched objects spatially, that is, getting closer and closer
to them, rather than the classic divide-and-conquer approach of other data structures. We analyze our method and show that
the number of distance evaluations to search among n objects is sublinear. We show experimentally that the sa-tree is the best existing technique when the metric space is hard to search or the query has low selectivity. These are the most
important unsolved cases in real applications. As a practical advantage, our data structure is one of the few that does not
need to tune parameters, which makes it appealing for use by non-experts.
Edited by R. Sacks-Davis Received: 17 April 2001 / Accepted: 24 January 2002 / Published online: 14 May 2002 相似文献
3.
Integrated spatial and feature image query 总被引:3,自引:0,他引:3
We present a new system for querying for images by regions and their spatial and feature attributes. The system enables the
user to find the images that contain arrangements of regions similar to those diagrammed in a query image. By indexing the
attributes of regions, such as sizes, locations and visual features, a wide variety of complex joint spatial and feature queries
are efficiently computed. In order to demonstrate the utility of the system, we develop a process for the extracting color
regions from photographic images. We demonstrate that integrated spatial and feature querying using color regions improves
image search capabilities over non-spatial content-based image retrieval methods. 相似文献
4.
Sunil Prabhakar Divyakant Agrawal Amr El Abbadi Ambuj Singh Terence Smith 《Multimedia Systems》2003,8(6):459-469
Abstract. With rapid advances in computer and communication technologies, there is an increasing demand to build and maintain large
image repositories. To reduce the demands on I/O and network resources, multi-resolution representations are being proposed
for the storage organization of images. Image decomposition techniques such as wavelets can be used to provide these multi-resolution images. The original image is represented by several coefficients, one of them
with visual similarity to the original image, but at a lower resolution. These visually similar coefficients can be thought
of as thumbnails or icons of the original image. This paper addresses the problem of storing these multi-resolution coefficients on disks so that thumbnail
browsing as well as image reconstruction can be performed efficiently. Several strategies are evaluated to store the image
coefficients on parallel disks. These strategies can be classified into two broad classes, depending on whether the access
pattern of the images is used in the placement. Disk simulation is used to evaluate the performance of these strategies. Simulation
results are validated with results from experiments with real Disks, and are found to be in good qualitative agreement. The
results indicate that significant performance improvements can be achieved with as few as four disks by placing image coefficients
based upon browsing access patterns.
Work supported by a research grant from NSF/ARPA/NASA IRI9411330 and NSF instrumentation grant CDA-9421978 and NSF Career
grant No. IIS-9985019, and NSF grant 0010044-CCR. 相似文献
5.
I/O scheduling for digital continuous media 总被引:4,自引:0,他引:4
A growing set of applications require access to digital video and audio. In order to provide playback of such continuous
media (CM), scheduling strategies for CM data servers (CMS) are necessary. In some domains, particularly defense and industrial process control, the timing requirements of these applications
are strict and essential to their correct operation. In this paper we develop a scheduling strategy for multiple access to
a CMS such that the timing guarantees are maintained at all times. First, we develop a scheduling strategy for the steady state,
i.e., when there are no changes in playback rate or operation. We derive an optimal Batched SCAN (BSCAN) algorithm that requires minimum buffer space to schedule concurrent accesses. The scheduling strategy incorporates two key
constraints: (1) data fetches from the storage system are assumed to be in integral multiples of the block size, and (2) playback
guarantees are ensured for frame-oriented streams when each frame can span multiple blocks. We discuss modifications to the
scheduling strategy to handle compressed data like motion-JPEG and MPEG.
Second, we develop techniques to handle dynamic changes brought about by VCR-like operations executed by applications. We define a suite of primitive VCR-like operations that can be executed. We show that an unregulated change in the BSCAN schedule, in response to VCR-like operations, will affect playback guarantees. We develop two general techniques to ensure playback guarantees while responding
to VCR-like operations: passive and active accumulation. Using user response time as a metric we show that active accumulation algorithms
outperform passive accumulation algorithms. An optimal response-time algorithm in a class of active accumulation strategies
is derived. The results presented here are validated by extensive simulation studies. 相似文献
6.
A. Savidis N. Maou I. Pachoulakis C. Stephanidis 《Universal Access in the Information Society》2002,1(4):274-287
The concept of ubiquitous computing reflects an infrastructure in which users are engaged in mobile interaction sessions within
environments composed of dynamically varying computational resources. In this paradigm, applications are required to continuously
follow end users and provide high-quality interaction while migrating among different computing devices and dynamically utilizing
the available input/output (I/O) resources of each device. In the context of such interaction scenarios, the principle of
continuity, which emphasizes the uninterrupted sequence of dialogue activities, is put forward as a key design goal. This
paper presents an application experiment demonstrating interface migration, distributed I/O control, and dynamic I/O reconfiguration.
The adopted dialogue design approach is discussed, along with the identified interaction design requirements, from the perspective
of dialogue continuity. Finally, the employed software engineering strategy is presented, elaborating on the way dialogue
mobility, distribution, and dynamic I/O control have been accomplished.
Published online: 11 June 2002 相似文献
7.
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. 相似文献
8.
In a multimedia server, multiple media streams are generally serviced in a cyclic fashion. Due to non-uniform playback rates
and asynchronous arrivals of queries, there tends to be spare disk bandwidth in each service cycle. In this paper, we study
the issue of dynamically using spare disk bandwidth and buffer to maximize the system throughput of a multimedia server. We
introduce the concept of minimizing buffer consumption as the criterion to select an appropriate media stream to utilize the spare system resources. Buffer consumption measures
not only the amount of buffer but also the amount of time such buffer space is occupied (i.e., the space-time product). Different
alternatives to utilizing spare disk bandwidth are examined, including different rate-adjustable retrievals of an already
activated stream and prefetching the next waiting stream. For rate-adjustable retrievals, we study buffer consumption-based and remaining-time-based criteria for selecting an active stream to increase retrievals. Simulations are conducted to evaluate and compare different
cases. The results show that (1) minimizing buffer consumption is the right criterion for maximizing the system throughput
with spare disk bandwidth; (2) in general, prefetching a waiting stream incurs more buffer consumption, and thus is less effective
than rate-adjustable retrieval of active streams in maximizing the system throughput; and (3) the advantage of rate-adjustable
retrieval over prefetching is especially significant when service cycle time is small. 相似文献
9.
Due to recent advances in network, storage and data compression technologies, video-on-demand (VOD) service has become economically
feasible. It is a challenging task to design a video storage server that can efficiently service a large number of concurrent
requests on demand. One approach to accomplishing this task is to reduce the I/O demand to the VOD server through data- and
resource-sharing techniques. One form of data sharing is the stream-merging approach proposed in [5]. In this paper, we formalize a static version of the stream-merging problem, derive an upper bound on the
I/O demand of static stream merging, and propose efficient heuristic algorithms for both static and dynamic versions of the
stream-merging problem. 相似文献
10.
Aya Soffer Hanan Samet 《The VLDB Journal The International Journal on Very Large Data Bases》1998,7(4):253-274
Symbolic images are composed of a finite set of symbols that have a semantic meaning. Examples of symbolic images include
maps (where the semantic meaning of the symbols is given in the legend), engineering drawings, and floor plans. Two approaches
for supporting queries on symbolic-image databases that are based on image content are studied. The classification approach
preprocesses all symbolic images and attaches a semantic classification and an associated certainty factor to each object
that it finds in the image. The abstraction approach describes each object in the symbolic image by using a vector consisting
of the values of some of its features (e.g., shape, genus, etc.). The approaches differ in the way in which responses to queries
are computed. In the classification approach, images are retrieved on the basis of whether or not they contain objects that
have the same classification as the objects in the query. On the other hand, in the abstraction approach, retrieval is on
the basis of similarity of feature vector values of these objects. Methods of integrating these two approaches into a relational
multimedia database management system so that symbolic images can be stored and retrieved based on their content are described.
Schema definitions and indices that support query specifications involving spatial as well as contextual constraints are presented.
Spatial constraints may be based on both locational information (e.g., distance) and relational information (e.g., north of).
Different strategies for image retrieval for a number of typical queries using these approaches are described. Estimated costs
are derived for these strategies. Results are reported of a comparative study of the two approaches in terms of image insertion
time, storage space, retrieval accuracy, and retrieval time.
Received June 12, 1998 / Accepted October 13, 1998 相似文献
11.
Daniel Hirschkoff 《International Journal on Software Tools for Technology Transfer (STTT)》2001,3(3):271-285
This paper investigates the use of the so-called up to techniques for bisimulation in the framework of verification. We first
introduce a method to exploit these techniques, that originate in theoretical works, in the applied context of verification.
We then apply it on the π-calculus, in order to design an up to bisimulation verification algorithm for π-calculus terms.
The outcome of such an effort is evaluated on two examples that were run on a prototype implementation.
Published online: 18 July 2001 相似文献
12.
Anne H.H. Ngu Quan Z. Sheng Du Q. Huynh Ron Lei 《The VLDB Journal The International Journal on Very Large Data Bases》2001,9(4):279-293
The optimized distance-based access methods currently available for multidimensional indexing in multimedia databases have
been developed based on two major assumptions: a suitable distance function is known a priori and the dimensionality of the
image features is low. It is not trivial to define a distance function that best mimics human visual perception regarding
image similarity measurements. Reducing high-dimensional features in images using the popular principle component analysis
(PCA) might not always be possible due to the non-linear correlations that may be present in the feature vectors. We propose
in this paper a fast and robust hybrid method for non-linear dimensions reduction of composite image features for indexing
in large image database. This method incorporates both the PCA and non-linear neural network techniques to reduce the dimensions
of feature vectors so that an optimized access method can be applied. To incorporate human visual perception into our system,
we also conducted experiments that involved a number of subjects classifying images into different classes for neural network
training. We demonstrate that not only can our neural network system reduce the dimensions of the feature vectors, but that
the reduced dimensional feature vectors can also be mapped to an optimized access method for fast and accurate indexing.
Received 11 June 1998 / Accepted 25 July 2000 Published online: 13 February 2001 相似文献
13.
We present a novel approach to the robust classification of arbitrary object classes in complex, natural scenes. Starting
from a re-appraisal of Marr's ‘primal sketch’, we develop an algorithm that (1) employs local orientations as the fundamental
picture primitives, rather than the more usual edge locations, (2) retains and exploits the local spatial arrangement of features
of different complexity in an image and (3) is hierarchically arranged so that the level of feature abstraction increases
at each processing stage. The resulting, simple technique is based on the accumulation of evidence in binary channels, followed
by a weighted, non-linear sum of the evidence accumulators. The steps involved in designing a template for recognizing a simple
object are explained. The practical application of the algorithm is illustrated, with examples taken from a broad range of
object classification problems. We discuss the performance of the algorithm and describe a hardware implementation. First
successful attempts to train the algorithm, automatically, are presented. Finally, we compare our algorithm with other object
classification algorithms described in the literature. 相似文献
14.
David Crandall Sameer Antani Rangachar Kasturi 《International Journal on Document Analysis and Recognition》2003,5(2-3):138-157
Abstract. The popularity of digital video is increasing rapidly. To help users navigate libraries of video, algorithms that automatically
index video based on content are needed. One approach is to extract text appearing in video, which often reflects a scene's
semantic content. This is a difficult problem due to the unconstrained nature of general-purpose video. Text can have arbitrary
color, size, and orientation. Backgrounds may be complex and changing. Most work so far has made restrictive assumptions about
the nature of text occurring in video. Such work is therefore not directly applicable to unconstrained, general-purpose video.
In addition, most work so far has focused only on detecting the spatial extent of text in individual video frames. However,
text occurring in video usually persists for several seconds. This constitutes a text event that should be entered only once
in the video index. Therefore it is also necessary to determine the temporal extent of text events. This is a non-trivial
problem because text may move, rotate, grow, shrink, or otherwise change over time. Such text effects are common in television
programs and commercials but so far have received little attention in the literature. This paper discusses detecting, binarizing,
and tracking caption text in general-purpose MPEG-1 video. Solutions are proposed for each of these problems and compared
with existing work found in the literature.
Received: January 29, 2002 / Accepted: September 13, 2002
D. Crandall is now with Eastman Kodak Company, 1700 Dewey Avenue, Rochester, NY 14650-1816, USA; e-mail: david.crandall@kodak.com
S. Antani is now with the National Library of Medicine, 8600 Rockville Pike, Bethesda, MD 20894, USA; e-mail: antani@nlm.nih.gov
Correspondence to: David Crandall 相似文献
15.
16.
Automated delineation of individual tree crowns in high spatial resolution aerial images by multiple-scale analysis 总被引:10,自引:0,他引:10
This paper presents an automatic multiple-scale algorithm for delineation of individual tree crowns in high spatial resolution
infrared colour aerial images. The tree crown contours were identified as zero-crossings, with convex grey-level curvature,
which were computed on the intensity image for each image scale. A modified centre of curvature was estimated for every edge
segment pixel. For each segment, these centre points formed a swarm which was modelled as a primal sketch using an ellipse
extended with the mean circle of curvature. The model described the region of the derived tree crown based on the edge segment
at the current scale. The sketch was rescaled with a significance value and accumulated for a scale interval. In the accumulated
sketch, a tree crown segment was grown, starting at local peaks, under the condition that it was inside the area of healthy
vegetation in the aerial image and did not trespass into a neighbouring crown segment. The method was evaluated by comparison
with manual delineation and with ground truth on 43 randomly selected sample plots. It was concluded that the performance
of the method is almost equivalent to visual interpretation. On the average, seven out of ten tree crowns were the same. Furthermore,
ground truth indicated a large number of hidden trees. The proposed technique could be used as a basic tool in forest surveys.
Received: 24 June 1997 / Accepted: 28 April 1998 相似文献
17.
Metrics for shot boundary detection in digital video sequences 总被引:5,自引:0,他引:5
The detection of shot boundaries in video sequences is an important task for generating indexed video databases. This paper
provides a comprehensive quantitative comparison of the metrics that have been applied to shot boundary detection. In addition,
several standardized statistical tests that have not been applied to this problem, as well as three new metrics, are considered.
A mathematical framework for quantitatively comparing metrics is supplied. Experimental results based on a video database
containing 39,000 frames are included. 相似文献
18.
To improve the discrimination power of color-indexing techniques, we encode a minimal amount of spatial information in the
index. We tesselate each image with five partially overlapping, fuzzy regions. In the index, for each region in an image,
we store its average color and the covariance matrix of the color distribution. A similiarity function of these color features
is used to match query images with images in the database. In addition, we propose two measures to evaluate the performance
of image-indexing techniques. We present experimental results using an image database which contains more than 11,600 color
images. 相似文献
19.
Xiaodong Wen Theodore D. Huffmire Helen H. Hu Adam Finkelstein 《Multimedia Systems》1999,7(5):350-358
We present several algorithms suitable for analysis of broadcast video. First, we show how wavelet analysis of frames of
video can be used to detect transitions between shots in a video stream, thereby dividing the stream into segments. Next we
describe how each segment can be inserted into a video database using an indexing scheme that involves a wavelet-based “signature.”
Finally, we show that during a subsequent broadcast of a similar or identical video clip, the segment can be found in the
database by quickly searching for the relevant signature. The method is robust against noise and typical variations in the
video stream, even global changes in brightness that can fool histogram-based techniques. In the paper, we compare experimentally
our shot transition mechanism to a color histogram implementation, and also evaluate the effectiveness of our database-searching
scheme. Our algorithms are very efficient and run in realtime on a desktop computer. We describe how this technology could
be employed to construct a “smart VCR” that was capable of alerting the viewer to the beginning of a specific program or identifying 相似文献
20.
Simonas Šaltenis Christian S. Jensen 《The VLDB Journal The International Journal on Very Large Data Bases》2002,11(1):1-16
Real-world entities are inherently spatially and temporally referenced, and database applications increasingly exploit databases
that record the past, present, and anticipated future locations of entities, e.g., the residences of customers obtained by
the geo-coding of addresses. Indices that efficiently support queries on the spatio-temporal extents of such entities are
needed. However, past indexing research has progressed in largely separate spatial and temporal streams. Adding time dimensions
to spatial indices, as if time were a spatial dimension, neither supports nor exploits the special properties of time. On
the other hand, temporal indices are generally not amenable to extension with spatial dimensions. This paper proposes the
first efficient and versatile index for a general class of spatio-temporal data: the discretely changing spatial aspect of
an object may be a point or may have an extent; both transaction time and valid time are supported, and a generalized notion
of the current time, now, is accommodated for both temporal dimensions. The index is based on the R-tree and provides means of prioritizing space versus time, which enables it to adapt to spatially and temporally restrictive
queries. Performance experiments are reported that evaluate pertinent aspects of the index.
Edited by T. Sellis. Received: 7 December 2000 / Accepted: 1 September 2001 Published online: 18 December 2001 相似文献