text:
|Numéro de publication
|Type de publication
|Numéro de demande
|Date de publication
|18 oct. 2007
|Date de dépôt
|14 juin 2007
|Date de priorité
|17 avr. 2006
|Autre référence de publication
|Numéro de publication
|Hugues Hoppe
|Cessionnaire d'origine
|Microsoft Corporation
|Exporter la citation
|BiBTeX, EndNote, RefMan
|Référencé par (21), Classifications (9), Événements juridiques (5)
|Liens externes: USPTO, Cession USPTO, Espacenet
This application is a Continuation-in-Part (CIP) of U.S. patent application Ser. No. 11/405,953, filed on Apr. 17, 2006, and entitled "PERFECT MULTIDIMENSIONAL SPATIAL HASHING."
1. Technical Field
The invention is related to perfect hashing for packing sparsely defined or sparsely distributed data into memory, and in particular, to perfect hashing of variable-rate data of one or more dimensions in an efficient randomly accessible format.
2. Related Art
In general, hashing is a well known technique for mapping data elements into a hash table by using a hash function to process the data for determining an address in the hash table. To cope with collisions (i.e., two or more data elements mapping to the same address in the hash table), hashing algorithms typically perform a sequence of probes into the hash table, where the number of probes varies per query. These probes provide collision detection by determining whether data has already been stored at a particular address in the hash table. Unfortunately, in time critical applications, such as image rendering in a graphics processing unit (GPU), this type of probing strategy is inefficient because GPU SIMD parallelism makes all pixels wait for the worst-case number of probes. Some GPUs can address this issue using dynamic branching; however, this is only effective if all pixels in a region follow the same branching path, which is unlikely for hash tests.
Avoiding excessive hash collisions and clustering generally requires a hash function that distributes data seemingly at random throughout the table. Consequently, hash tables often exhibit poor locality of reference, resulting in frequent cache misses and high-latency memory accesses. Perfect hashing addresses some of these problems by using a hash function that maps elements into a hash table without any collisions, such that all the elements map to distinct slots of the hash table.
In theory, perfect hash functions are rare in the space of all possible functions. In fact, the description of a minimal perfect hash function (wherein all slots in the hash table are filled) theoretically requires a number of bits proportional to the number of data entries. Consequently, it is not generally feasible to construct a perfect hash using an expression with a small number of machine-precision parameters. Instead, additional data is generally stored in auxiliary lookup tables for use in combination with the hash table.
Typical perfect hashing schemes have generally focused on external storage of data records indexed by character strings or sparse integers. Consequently, conventional perfect hashing schemes are generally not well adapted for use with spatially coherent multidimensional data. For example, in typical computer graphics applications, 2D and 3D texture data is often accessed coherently by the GPU (i.e., adjacent or nearby image patches or segments are accessed either sequentially or in parallel by the GPU). This texture data is then swizzled, tiled, cached, etc. by the GPU. Unfortunately, typical hash functions do not generally exploit the spatial coherence issues of such data when accessing that data.
Further, many images, such as, for example, vector images or graphics, involve sparsely defined spatial data. In particular, with these types of images, image discontinuities such as sharp vector silhouettes are generally present at only a small fraction of pixels. Texture sprites often overlay high-resolution features at sparse locations. Image attributes such as alpha masks are mainly binary, requiring additional resolution at only a small subset of pixels. In addition, surface textures or geometries can be also represented as sparse 3D data. Further, such data can be encoded using variable rates, such as where various cells of a grid-based vector image have a differing amount of complexity. However, compressing this type of variable-rate sparse data while retaining efficient random-access is a problem that has not been addressed by conventional perfect hashing schemes.
Spatial hashing is another conventional hashing technique that is commonly used for point and region queries in multidimensional databases. Spatial hashing is also used in graphics for efficient collision detection among moving or deforming objects. However, these techniques generally employ imperfect hashing (e.g., traditional multi-probe hash tables implemented on the CPU). Further, these techniques do not transition to multidimensional tables. Also, they strive to make intermediate hashes as random as possible. Consequently, conventional spatial hashes are not well adapted for use with sparsely defined spatial data such as vector graphics.
This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.
A "Variable-Rate Perfect Hasher," as described herein, extends the concepts of perfect spatial hashing described in the aforementioned co-pending U.S. patent application Ser. No. 11/405,953 to address the issue of handling variable-sized data elements of one or more dimensions. Consequently, the Variable-Rate Perfect Hasher extends perfect hashing to consider sparsely distributed data records where each sparse data record can have a different size. In other words, the data associated with the sparse data points is variable-sized. This concept is referred to herein as hashing of "variable-rate" or "variable-size" data. Note that in the parent application (U.S. patent application Ser. No. 11/405,953), perfect hashing was directed primarily towards hashing of spatially coherent fixed-rate data. However, the Variable-Rate Perfect Hasher described herein is specifically adapted for use with variably sized data elements which may or may not have some amount of spatial coherence or may be distributed randomly in space.
In general, the Variable-Rate Perfect Hasher provides a process for densely packing sparse variable-rate data into a perfect hash table. More specifically, the Variable-Rate Perfect Hasher generally operates by creating a hash table in combination with an offset table of one or more dimensions. A perfect hash is created by mapping sparse variable-rate data of one or more dimensions into the hash table using the offset table. Values of entries in the offset table are carefully chosen or optimized such that no hash collisions will occur in the resulting perfect hash table. Note that while the Variable-Rate Perfect Hasher can hash data whether or not that data is sparse, the size of the offset table directly corresponds to the sparsity of the data being hashed. In particular, as the number of data elements increases, the size of the resulting offset table will also increase.
This packing technique is ideally suited for hashing many types of sparse data since it eliminates the need to perform collision checks by ensuring a perfect hash. For example, in one embodiment, a variable-rate perfect hash is a useful data structure for providing random-access to variable-sized data elements associated with some spatial domain. One simple example of variable-rate data is a sparsely populated grid-based array of data where each populated "cell" of the grid has varying amounts of information. One such application for a 2-D case is to store information about vector graphics within the cells of an image (wherein a grid is used to divide the vector image into a set of grid-based cells). In a 1-D case, a simple example would be to store a variable-length record with a sparse set of integers in a corresponding perfect hash using an offset table.
Another application is to store image residual information after image compression. For example, as is well known to those skilled in the art, image compression is generally lossy, such that some information gets lost every time an image is encoded. This loss of detail is generally higher in regions of the image that contain greater levels of detail. Consequently, in one embodiment, rather than losing such data, the Variable-Rate Perfect Hasher encodes these areas of high detail in a sparse residual layer, which is then stored using a variable-rate perfect hash, as described herein.
Clearly, given these capabilities, the Variable-Rate Perfect Hasher is useful for a large number of applications, including, for example, computer graphics applications involving sparse data, such as sharp image silhouettes, texture sprites, alpha channel compression, 3D-parameterized textures, 3D painting, simulation, collision detection, preserving residual data following image compression, etc. However, it should also be clear that the Variable-Rate Perfect Hasher is not intended to be limited to the hashing of image data, and that any type of variable-rate data of any dimensionality can be hashed using the techniques described herein.
In view of the above summary, it is clear that the Variable-Rate Perfect Hasher described herein provides a unique system and method for mapping variable-rate data into a hash table using a perfect hash function, and that the resulting hash tables support efficient random access of the variable-sized data elements stored therein. In addition to the just described benefits, other advantages of the Variable-Rate Perfect Hasher will become apparent from the detailed description that follows hereinafter when taken in conjunction with the accompanying drawing figures.
The specific features, aspects, and advantages of the present invention will become better understood with regard to the following description, appended claims, and accompanying drawings where:
In the following description of the preferred embodiments of the present invention, reference is made to the accompanying drawings, which form a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention.
1.0 Exemplary Operating Environments:
For example,
The invention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held, laptop or mobile computer or communications devices such as cell phones and PDA's, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.
The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer in combination with various hardware modules. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices. With reference to
Components of computer 110 may include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including the system memory to the processing unit 120. The system bus 121 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.
Computer 110 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data.
Computer storage media includes, but is not limited to, RAM, ROM, PROM, EPROM, EEPROM, flash memory, or other memory technology; CD-ROM, digital versatile disks (DVD), or other optical disk storage; magnetic cassettes, magnetic tape, magnetic disk storage, or other magnetic storage devices; or any other medium which can be used to store the desired information and which can be accessed by computer 110. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term "modulated data signal" means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared, and other wireless media. Combinations of any of the above should also be included within the scope of computer readable media.
The system memory 130 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input/output system 133 (BIOS), containing the basic routines that help to transfer information between elements within computer 110, such as during start-up, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 120. By way of example, and not limitation,
The computer 110 may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only,
The drives and their associated computer storage media discussed above and illustrated in
Other input devices (not shown) may include a joystick, game pad, satellite dish, scanner, radio receiver, and a television or broadcast video receiver, or the like. These and other input devices are often connected to the processing unit 120 through a wired or wireless user input interface 160 that is coupled to the system bus 121, but may be connected by other conventional interface and bus structures, such as, for example, a parallel port, a game port, a universal serial bus (USB), an IEEE 1394 interface, a Bluetooth™ wireless interface, an IEEE 802.11 wireless interface, etc. Further, the computer 110 may also include a speech or audio input device, such as a microphone or a microphone array 198, as well as a loudspeaker 197 or other sound output device connected via an audio interface 199, again including conventional wired or wireless interfaces, such as, for example, parallel, serial, USB, IEEE 1394, Bluetooth™, etc.
A monitor 191 or other type of display device is also connected to the system bus 121 via an interface, such as a video interface 190. In addition to the monitor, computers may also include other peripheral output devices such as a printer 196, which may be connected through an output peripheral interface 195.
The computer 110 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 180. The remote computer 180 may be a personal computer, a server, a router, a network PC, a peer device, or other common network node, and typically includes many or all of the elements described above relative to the computer 110, although only a memory storage device 181 has been illustrated in
When used in a LAN networking environment, the computer 110 is connected to the LAN 171 through a network interface or adapter 170. When used in a WAN networking environment, the computer 110 typically includes a modem 172 or other means for establishing communications over the WAN 173, such as the Internet. The modem 172, which may be internal or external, may be connected to the system bus 121 via the user input interface 160, or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer 110, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation,
With respect to
At a minimum, to allow a device to implement the functionality of the Variable-Rate Perfect Hasher, the device must have some minimum computational capability, some storage capability, an interface for allowing input and encoding of variable-rate data. In addition, this simplified computing device may also include an output device.
In particular, as illustrated by
In addition, the simplified computing device of
The exemplary operating environment having now been discussed, the remaining part of this description will be devoted to a discussion of the program modules and processes embodying a "Variable-Rate Perfect Hasher" which provides a process for densely packing sparse variable-rate data into a perfect hash table using an offset table constructed directly from the data being hashed.
2.0 Introduction:
Perfect hashing is a concept that is known to those skilled in the art. For example, a perfect hash usually refers to a hash function that maps elements into a hash table without any collisions. Generally, all the elements map to distinct slots of the hash table. The probability that randomly assigning n elements in a table of size m results in a perfect hash is given by Equation 1, where:
When the table is large (i.e., when m>>n), the probability of a perfect hash, pph, can be determined by using the approximation ex≈1+x for small x, as illustrated by Equation 2, where:
Thus, the presence of a hash collision is highly likely when the table size m is much less than n2. This is an instance of the well-known "birthday paradox" (e.g., a group of only random 23 people have more than 50% chance of having at least one shared birthday).
The probability of finding a minimal perfect hash (e.g., where n=m) is given by Equation 3, where:
which uses Stirling's approximation: log n!≅n log n−n. Therefore, the expected number of bits needed to describe these rare minimal perfect hash functions is given intuitively by Equation 4, where:
Several number-theoretical methods construct perfect hash functions by exploiting the well known Chinese remainder theorem. However, even for sets of a few dozen elements, these functions involve integer coefficients with hundreds of digits. On the other hand, a more computer-amenable approach is to define the hash using one or more auxiliary tables. For example, one conventional approach uses three such tables and two nested hash functions to hash a sparse set of n integers taken from
Other conventional schemes treat perfect hashing as an instance of sparse matrix compression. Such schemes map a bounded range of integers to a 2D matrix and compact the defined entries into a 1D array by translating the matrix rows. However, sparse matrix compression is known to be a NP-complete complete problem.
Other, more practical, schemes achieve compact representations and scale to larger datasets by giving up guarantees of success. These probabilistic constructions generally iterate over several random parameters until finding a solution. For example, one such scheme defines a hash as illustrated by Equation 5, where:
h(k)=h 0(k)+g 1[(h 1(k)]+g 2[(h 2(k)] mod(
where functions h0, h1, and h2 map string keys k to
Another conventional approach to perfect hashing involves adapting the hashing scheme described with respect to Equation 5 to create provide a hashing scheme that provides generally acceptable average-case performance (˜11n bits) on large datasets. The insight provided to enable this scheme is assign values of auxiliary tables g1 and g2 in decreasing order of number of dependencies. A closely related approach provides a hashing scheme that uses quadratic hashing and adds branching based on a table of binary values. This scheme is generally more efficient in that it achieves ˜4n bits for datasets on the order of size n˜106.
2.0.1 Perfect Hashing:
In general, a perfect hash which considers spatial coherence of fixed-rate data is defined using a hash function and offset table as illustrated by Equation 6, where:
h(p)=h 0(p)+Φh 1(p) Equation 6
where h0 and h1 are both imperfect hashes that are combined using an offset table Φ. Intuitively, the role of the offset table, Φ, is to "jitter" the imperfect hash function h0 into a perfect one. Although the offset table uses additional memory, it is significantly smaller than the data itself (e.g., it typically has only around 15-25% as many entries as the hash table itself). Further, with respect to image data, such as vector graphics, this technique can be implemented within various types of processors, such as, for example a programmable GPU, where this format for defining a perfect hash allows data access using just one additional texture access plus approximately 4-6 more shader instructions depending on the application scenario.
Unlike various conventional perfect hashing techniques that make intermediate hash functions h0, and h1 as random as possible, the perfect spatial hashing enabled with respect to Equation 6 instead designs these hash functions to be spatially coherent, resulting in efficient access into the offset table Φ, and enabling random access into the resulting hash table. Furthermore, this perfect hashing optimizes the offset values in Φ to maximize spatial coherence of the hash table itself. Creating a perfect hash is typically a difficult combinatorial problem. However, there are enough degrees of available freedom to improve overall spatial coherence and thereby increase runtime hashing performance.
For applications that require continuous local interpolation of the sparse data, there are various approaches to perfect hashing. For example, in one embodiment, for processing sparse image data in a GPU, native filtering is used in dedicated GPU hardware by grouping the data into sample-bordered blocks. In this embodiment, traditional block indirection tables are replaced with a compact spatial hash over the sparsely defined blocks. The limiting factor in using blocks is that data must be duplicated along block boundaries, thus discouraging small blocks sizes and leading to memory bloat.
The Variable-Rate Perfect Hasher described herein further improves the perfect spatial hashing techniques summarized above by enabling perfect hashing of sparsely defined variable-rate data (i.e., perfect hashing of variable-sized data elements), with the resulting perfect hash also being applicable to each of the embodiments discussed with respect to perfect hashing of fixed-rate data.
2.1 System Overview:
As noted above, the Variable-Rate Perfect Hasher described herein operates to pack variable rate (i.e., non-uniform) sparse data into a memory structure such as a table or memory buffer. In general, this data packing is achieved using a variable-rate perfect hash technique that uses an offset table constructed from the positions or addresses of the data being hashed to provide faster hashing (no need for collision checking). Hash table addresses are computed for hashing each variable-rate data element based on parameters of each data element and a corresponding offset vector stored in the offset table. In addition, the techniques described herein also provide quicker access to specific spatial regions of the encoded data since that data can be encoded in contiguous regions of memory (i.e., the hash table) that are randomly accessible.
Further, unlike the data typically processed using conventional perfect hash functions, the data elements or records being hashed by the Variable-Rate Perfect Hasher are variable-sized and therefore stored as variable length strips or strings in the resulting hash table. In particular, conventional perfect hashing techniques operate on the assumption that data elements or records being hashed are represented by the same number of bits. However, in many real-world applications, such data elements can have variable-lengths representing varying levels of complexity or information. Consequently, in contrast to conventional hashing techniques, the Variable-Rate Perfect Hasher considers this variable length to develop a unique data structure for packing the data into memory using a technique referred to herein as "variable-rate perfect hashing."
Note that since the data elements being stored in the hash table are variable-sized and the individual storage elements, slots, or cells of the hash table are fixed in size, each hashed data element will occupy one or more contiguous storage elements in the hash table. For example, for a 2-D hash table having a plurality of rows of data, a hashed data element might take the form of a "strip" or "string" covering one or more contiguous storage elements of the hash table (and possibly wrapping across one or more rows of storage elements). This data strip would begin at the computed hash table address and continue across as many contiguous elements of the hash table as necessary to encompass the entirety of the variable-rate data element being hashed. Clearly, whether data elements are stored as strips or in some other contiguous arrangement or block of data elements in the hash table will depend upon the dimensionality of the hash table. Therefore, for purposes of discussion, hashed data elements will generally be referred to herein as a "data strip" or "data string" or simply as encompassing a contiguous block of storage elements within the hash table.
As described in greater detail in the following paragraphs, the Variable Rate Perfect Hasher is capable of hashing any type of sparsely defined variable-rate data. One simple example of this type of variable-rate data is a sparsely populated grid-based array of data where each populated "cell" of the grid has varying amounts of information. In this case, a "cell" of the grid has a known address or location that is used both in constructing the offset table used in hashing the data, and in providing random access to the corresponding data in the hash table. However, it should be noted that in view of the following discussion, the Variable-Rate Perfect Hasher is not intended to be limited to the hashing of grid-based data cells, and that any type of variable-rate data can be hashed using the techniques described herein.
2.2 System Architectural Overview:
The processes summarized above are illustrated by the general system diagram of
In general, as illustrated by
Next, the data elements 300 are provided to an offset table construction module 310. The offset table construction module 310 examines each data element 300 in combination with the address or location of that data element in the domain of data elements, and uses that information to determine an offset vector to be assigned to a corresponding entry in an offset table 330. As described in greater detail in Section 3, these offset vectors are assigned to an entry in the offset table 330 such that while two or more data elements may map to the same offset vector, there are still no collisions in the resulting hash table 350.
For example, the hash table 350 is necessarily as large as the number of data elements 300 defined in the domain since it must contain all of those data elements. However, the offset table 330 is smaller than the number of data elements since it is allowable to have two or more of those data elements mapping to the same offset vector. Thus, assigning an offset vector in the offset table 330 has the effect of displacing/translating the hash addresses of one or more data elements in the resulting hash table 350. As such, the purpose of the offset vector assignments is to have all data elements 300 map to unique hash addresses in the hash table 350 even if those data elements have the same offset vectors in the offset table 330.
To ensure that none of the offset vectors for the data elements result in hash table 350 collisions, thereby ensuring a perfect hash, the offset table construction module 310 uses a perfect spatial hash function that considers all possible offset vectors (starting from a random one) for packing the variable sized data elements or records into memory until finding an offset vector that does not create any hash collisions. A hash table construction module 340 then assigns the data strips corresponding to each data element 300 to an address in the hash table 350 computed as a joint function of the corresponding offset vector and a hash of that data element.
In particular, the offset table construction module 310 first determines the sum of the data strip sizes (assuming one or more data elements 300 mapping to the same offset vector) for all of the data elements 300 (i.e., the domain points) mapping to a particular offset table entry. Then, the sum of data strips sizes is used to determine the order in which offset vector entries are evaluated for determining hash table addresses. Specifically, the offset vectors entries are evaluated in order of decreasing sum of data strip sizes for the data elements 300 associated with each particular offset vector entry. Then, using this sum-based evaluation order, for each selected offset vector entry, the offset table construction module 310 searches over all possible offset vector value assignments until finding one that results in zero collisions with data placed so far in the hash table 340.
If no valid offset vector value is found, then an offset table size module 320 resets offset table construction to the beginning using a larger offset table size, with the processes described above then being repeated until successful construction of the complete offset table 330 and the corresponding perfect hash table 350. Note that these processes are guaranteed to terminate if the offset table becomes large enough, since at some size (depending upon the size of the data domain) each offset table entry would only reference a single domain point.
In addition, since the data elements 300 are considered sparse over the extents of the data domain, some of the data elements of the domain will not contain any data. Therefore, in one embodiment, a mask construction module 360 checks each point in the domain to determine whether the corresponding data element contains any data. A simple mask 370 is then created by the mask construction module to identify those domain points containing data (or conversely, those domain points that do not contain data). For example, in one embodiment, a single bit (i.e., "0" or "1") is assigned to every domain point to indicate whether that domain point contains any data. Then, both when constructing the offset table 330 and populating the hash table 350, the mask 370 is consulted for each point to ensure that only those domain points having data are assigned offset vectors in the offset table and hashed to the hash table. Note that as described in further detail in section 3.6 with respect to
Further, as discussed in further detail below in Section 3.6, this mask 370 can then be used when randomly accessing data in the hash table 350. For example, in one embodiment, whenever data for a particular domain point is requested, the mask 370 is first checked to determine whether there is actually any data for the selected domain point. If the mask 370 indicates that a particular domain point does not contain any data, then no further processing of that domain point needs to be performed. On the other hand, if the mask indicates that there is data for the selected domain point, then the hash table 350 will be consulted to retrieve the corresponding data.
3.0 Operation Overview:
The above-described program modules are employed for implementing the Variable-Rate Perfect Hasher. As summarized above, the Variable-Rate Perfect Hasher operates to pack or hash variable-rate spatially coherent data into a memory structure such as a table or memory buffer in a randomly accessible format by using an offset table constructed from the data being hashed in combination with a hash function that together provide perfect hashing of the variable rate data. The following sections provide a detailed discussion of the operation of the Variable-Rate Perfect Hasher, and of exemplary methods for implementing the program modules described in Section 2 with respect to
3.1 Operational Details of the Variable-Rate Perfect Hasher:
The following paragraphs detail specific operational and alternate embodiments of the Variable-Rate Perfect Hasher described herein. In particular, the following paragraphs describe perfect hashing of sparse spatially coherent fixed-rate data, as detailed in co-pending U.S. patent application Ser. No. 11/405,953. Then, given this background using fixed-rate data, a detailed discussion relating to applying these techniques to hashing of variable rate data is provided. Specifically, the following paragraphs describe details of a perfect spatial hash and general terminology used in describing perfect spatial hashing; hash construction for fixed-rate data; graphics processor unit (GPU) implementation; perfect spatial hashing of variable-rate data; and efficient random access of hashed data.
3.2 Perfect Spatial Hash Overview:
In general,
the sparse data consists of a subset S⊂U of n grid positions, where each position pεS has associated data record D(p). Thus, the data density is the fraction=n/u. For datasets of co-dimension 1, such as curves in 2D or surfaces in 3D, ρ can be typically be approximated as ρ=1/
The basic idea with perfect spatial hashing is to replace the sparsely defined data D(p) by a densely packed hash, H[h(p)], where:
As illustrated by
h(p)=(h 0(p)+Φ[h 1(p)mod
In this example, the offset table Φ 406 is a d-dimensional array of size r=
3.3 Hash Construction for Fixed-Rate Data:
In constructing a perfect hash for fixed-rate data, it is necessary to find hash table size
3.3.1 Selection of Table Sizes:
As noted above, the hash table can be any dimensionality, d, that is desired. For example, a 2D hash table, with d=2, might represent an image grid, or a 3D hash table, with d=3, might represent a volumetric grid of a 3D model. Further, the sizes of the axes of the hash table can be arbitrary. However, for purposes of explanation, the following discussion assumes that all the axes of the hash table have the same size,
Next, a size,
For example, in one embodiment, a value of
Alternately, for the most compact construction, a binary search over
It has been observed that hash construction is less effective if
3.3.2 Selection of Hash Coefficients:
In one embodiment, the hash coefficient matrices M0 and M1, for hash functions h0 and h1, respectively, are filled with random prime coefficients. However, better hashing performance is achieved by making these matrices more regular.
Specifically, allowing the hash coefficient matrices M0 and M1 to be identity matrices does not significantly hinder the construction of a perfect hash. In this case, the functions h0 and h1 simply wrap the spatial domain multiple times over the offset and hash tables, moving over domain points and table entries in lockstep. As a result, the offset table access Φ[h1(p)] is perfectly coherent. Although h0(p) is also coherent, the hash table access H[h(p)] is generally not coherent because it is jittered by the offsets. However, if adjacent offset values in Φ are the same (e.g., if the offset table is locally constant), then h itself will also be coherent. See Section 3.3.4 for additional discussion regarding these coherence issues.
One necessary condition on functions h0 and h1 is that they must map the defined data to distinct pairs. In other words, pεS→(h0(p),h1(p)) must be injective. Note that an injective function is one which associates distinct arguments to distinct values such that a function ƒ is injective if it maps distinct values of x in the domain to distinct values of y in the codomain, such that ƒ(x)=y. Note that, given two points (p1,p2)εS, with h0(p1)=h0(p2) and h1(p1)=h1(p2), then these points would always hash to the same slot, i.e., h1(p1)=h2(p2), regardless of the offset stored in Φ[h1(p1)] making a perfect hash impossible.
Consequently, the condition for injectivity is similar to a perfect hash of n elements into a table of size |H|×|Φ|=mr. A probability of success, pph, for a perfect hash, can be computed as illustrated by Equation 8, where:
p ph ≅e −n
This probability, pph is typically a fairly low probability, e.g., only about 12% for σ=r/n=0.25. For this reason, conventional perfect hashing schemes often resort to additional tables and hash functions to improve the probability of a perfect hash.
However, in contrast to conventional perfect hashing schemes, the perfect spatial hashing described herein does not involve selecting h0 and h1 to be random functions. In fact, because the functions h0 and h1 have periodicities
3.3.3 Offset Table Creation:
Those entries Φ[q] with the largest sets h1 −1(q) of dependent data points are most difficult to assign to the hash table. Consequently, these values are processed first. Offset values are assigned using a "greedy" approach according to this heuristic order (e.g., computed efficiently using a bucket sort). In particular, for each entry q, a search for an offset value Φ[q] is made such that the data entries h1 −1(q) do not collide with any data previously assigned in the hash table 404, as illustrated by Equation 9, where undefined (i.e. unassigned) values in the hash table are identified as follows:
∀pεh 1 −1(q), H[h 0(p)Φ[q]]=undef Equation 9
Assuming the use of 8-bits for quantizing offset values, the space of offset values is
Note that in the example of
3.3.4 Optimization of Hash Coherence:
As noted above, when M1 is defined as an identity matrix, accesses to the offset table Φ are always coherent. The following paragraphs describe how hash construction is optimized to increase coherence of access to H.
First, in the case where hash queries are constrained to the set of defined entries S⊂U, then NS(p1, p2) is "1" if two defined points, p1, p2 εS, are spatially adjacent in the domain (i.e., ∥p1−p2∥=1), or "0" otherwise. In addition, in this case, NH(s1, s2) is similarly defined for slots in H. Given these parameters, NH is maximized as illustrated by Equation 10, where:
This second expression for NH is then measured during hash construction. When assigning an offset value Φ[q], rather than simply selecting any valid value, values that maximize coherence are selected. In particular, the slots of H into which the points h1 −1(q) map are examined, ant the number of neighbors in H that are also neighbors in the spatial domain are counted, as illustrated by Equation 11, where:
While a brute force approach for testing every possible value for Φ[q] is performed in one embodiment, it is generally more computationally efficient to limit the number of candidates being tested. Consequently, in one embodiment, possible values for Φ[q] are limited using the following heuristics:
In the case that hash queries span the full domain U, then local constancy of Φ is most important. Therefore, in this case, preference is given to the candidates found using Equation 13, as illustrated above.
In addition, in one embodiment, as a post-process, any undefined offset entries (i.e., for which h1 −1(q)=Ř) are assigned values coherent with their neighbors using a normalized coherence metric such as ŃH=NH/Σp
3.3.5 Sparsity Encoding:
The hash table generally stores data associated with a sparse subset of the overall domain. Depending on the application, it may be necessary to determine if an arbitrary query point lies in this defined subset. In other words, since the data is sparse, some arbitrary data points within the overall domain may not contain any data. Consequently, as noted above, in various embodiments, when an arbitrary point within the domain is selected for random access (either by a user, or automatically) the Variable-Rate Perfect Hasher first determines whether that particular point includes any data.
Some data access scenarios, such as 3D-parameterized surface textures, guarantee that only the defined subset of the domain (i.e., points having data) will ever be accessed. In this case, it is not necessary for the Variable-Rate Perfect Hasher to determine whether a selected point has data before attempting to retrieve that data from the hash table.
However, for scenarios involving unconstrained access, where any point in the total domain may be selected, whether that point includes data or not, a binary image (i.e., the aforementioned "mask," see
In the case that the particular GPU being used lacks support for single-bit textures, the above described mask-based embodiment can still be enabled by packing each 4×2 block of domain bits into one pixel of an 8-bit luminance image. Then, to dereference the bit, a lookup is performed in a corresponding 4×2×256 texture.
In contrast, if a non-sparse image is already defined over the domain, a related embodiment operates to hide domain bits within this image for one or more points of the domain. For example, such data can be included as the least-significant bit of a color or alpha channel, or in some other location where it will not change modify other data. This use of a hidden bit is convenient to indicate the presence of sparse supplemental data beyond that in the normal image. For example, as is well known to those skilled in the art, image compression is generally lossy, such that some information gets lost every time an image is encoded. This loss of detail is generally higher in regions of the image that contain greater levels of detail.
Consequently, in one embodiment, rather than losing such data, the Variable-Rate Perfect Hasher encodes these areas of high detail in a sparse residual layer, which is then stored using a variable-rate perfect hash, as described herein. Then, when decoding or rendering that image, the bits hidden in the image indicate whether the stored residual information is to be used for a particular point in the image. Note that the reference to a "point" here, and throughout this document, does not necessarily refer to an individual pixel, and that as described above, a "point" within the overall domain simply represents some region or subset of the overall domain. Therefore, in the case of an image, a "point" in the domain can represent one or more pixels, depending upon a level of zoom and a size of the image and the cells or points in the domain.
When the data is very sparse, storing even a single bit per domain point may take significant memory. Consequently, in one embodiment, the Variable-Rate Perfect Hasher includes a tag in each slot of the hash table to identify the domain position {circumflex over (p)} of the stored data. Then, given a query point, the Variable-Rate Perfect Hasher can then simply compare it with the stored tag.
In particular, encoding a position {circumflex over (p)}εU requires a minimum of log2 u bits. The position tags can be stored in an image with d channels of 16 bits, thus allowing a domain grid resolution of
3.4 GPU Implementation:
As noted above, various embodiments of the Variable-Rate Perfect Hasher can be implemented within a programmable graphics processing unit (GPU) which is designed for fast access to array-based data. For example, by using arrays with integer coordinates (e.g., 0, 1, . . . ,
and normalized colors
Quantizing the offset vectors stored in the offset table, Φ, to 8 bits per coordinate provides enough flexibility for hashing even when the hash table size
This idea is represented by the high-level shading language (HLSL) pseudo-code for the exemplary hashing function, as shown in Table 1:
TABLE 1 Pseudo-Code for Hashing in a GPU static const int d=2; // spatial dimensions (2 or 3) typedef vector<float,d> point; #define tex(s,p) (d==2 ? tex2D(s,p) : tex3D(s,p)) sampler SOffset, SHData; // tables Φ and H. matrix<float,d,d> M[2]; // M0, M1 prescaled by 1/ respectively. point ComputeHash(point p) { // evaluates h(p) → [0, 1]d point h0 = mul(M[0],p); point h1 = mul(M[1],p); point offset = tex(SOffset, h1) * oscale; // (* ┌ return h0 + offset; } float4 HashedTexture(point pf) : COLOR { // pf is prescaled into range [0, point h = ComputeHash(floor(pf)); return tex(SHData, h); }
In various embodiments, several additional optimizations of the pseudo-code illustrated in Table 1 are implemented. For example, for 2D domains, the two matrix multiplications (i.e., (mul(M[i],p)) are performed in parallel within a float4 tuple. In addition, in another embodiment, since the matrices M0 and M1 are in fact scaled identity matrices, the matrix multiplications are reduced to a single multiply instruction.
3.5 Perfect Spatial Hashing of Variable-Rate Data:
The basic ideas and for perfect spatial hashing for fixed-rate data described above cannot be directly used for variable-rate data (i.e., data elements having variable sizes). However, several of the above described processes are modified, as described in further detail below, to enable the Variable-Rate Perfect Hasher to handle such data. It should be noted that extending these capabilities to address variable-rate data also enables each of the additional fixed-rate embodiments described above to be performed using variable-rate data.
In general, as with fixed rate data, to enable processing of variable-rate data, the Variable-Rate Perfect Hasher, the hash function is again defined using an offset table. In other words, the location of the hashed data elements within the hash table are determined by adding the original cell position of the variable rate-data element to an offset vector retrieved from the offset table. Similarly, both the first access to the offset table and the subsequent access into the hash table are performed using modulo addressing (also referred to as "wraparound addressing"), as described herein.
In general, construction of the offset table proceeds in a similar manner to that described in Section 3.3. For example, for each offset table entry, the Variable-Rate Perfect Hasher assigns an offset vector, Φ[q], such that the hashed data elements for the domain points that map to that offset table entry do not collide with hashed data elements for any other domain point.
For fixed-rate data, a greedy heuristic algorithm, as described above, operated to assign offset vectors in order of decreasing number of dependencies. In other words, offset table entries onto which the most domain points mapped for the fixed-rate data case were identified and assigned those offset vectors first. In contrast, this general strategy is extended to variable-rate data by instead considering the sum of the data record sizes for the domain points mapping to a particular offset table entry.
For example, for each selected offset vector entry, the Variable-Rate Perfect Hasher searches over all possible offset vector value assignments until finding one that results in zero collisions with data placed so far in the hash table. If no valid offset vector value is found, then the process is aborted, and a larger offset table size is used in repeating the search for offset vector value assignments, and so on until no collisions occur.
More specifically, assuming that e(p) denotes a variable strip size of some variable-rate cell or data element p. Then, the hash, h(p), is defined using a 2D offset table Φ, such that the hash function h(p) is given by Equation 14, where:
h(p)=(p+Φ[p mod(
The construction of the offset table Φ uses a heuristic strategy wherein offset vectors Φ[q] are assigned in order of decreasing number of dependent data elements. Then, rather than counting the number |h1 −1(q)| of dependent data records, where h1(p)=p mod(
Then, using this sum-based evaluation order, to assign the offset vectors, Φ[q], for this variable-rate case, the Variable-Rate Perfect Hasher considers all possible offset vectors (starting from a random one) until finding one that does not create any hash collisions. In one embodiment, spatial coherence of the data elements is considered by attempting to place hashed data strips adjacent to each other by first performing the traversal until finding an invalid offset vector (i.e., one resulting in a collision) and then looking for the first (and thus closest) valid offset vector.
3.5.1 Data Structure for Variable-Rate Data:
It has been observed that data structures do not generally support efficient random access to variable-sized data records. However, the data structures created by the Variable-Rate Perfect Hasher are an exception to this observation. In particular, as noted above, each domain cell p of the hash table contains a variable-size data record e(p), wherein the size e(p)≧0, with a value of "0" representing no data for a particular data record. Consequently, the total data size, E, for all records stored in the hash table is given by Equation 15, where:
E=Σ p |e(p) Equation 15
Note that the size of each data record is encoded in the data itself, so the data structure need to explicitly store |e(p)|. Alternately, |e(p)| can be encoded in the hashed data string so that data size can be explicitly read from that data. However, this embodiment will require some small amount of additional data to be included in the hashed data strings.
Similarly to the fixed-rate examples described above, the total number of defined cells (i.e., cells that have some data) is given by Equation 16, where:
n=Σ p,|e(p)>01 Equation 16
In other words, the number of defined cells, n, is simply a count of the total number of cells in the sparse domain that have some non-zero data.
Therefore, m≅E, m≧E, and r∝n, where, as described above, r and m are the sizes of the offset table, Φ, and the hash table, h, respectively. In other words, the size, r, of the offset table for use with variable rate data is proportional to the number of cells, n, in the sparse domain having non-zero data. Further, the size, m, of the hash table is approximately equal to, but never less than, the total size, E, of the non-zero data records.
As noted above, each data record is stored as a strip, e(p), of some variable length, within the 2D hash table. The perfect hash function points to the beginning of the strip. As noted above, offset vector values, Φ[q], are assigned in order of decreasing number of "dependencies". However, rather than counting the number |h−1(q)|=Σpεh
Then, when considering the assignment of an offset vector, q, the Variable-Rate Perfect Hasher checks that for each dependent domain cell, pεh1 −1(q), the resulting strip in the hash table is currently empty along the entire length of that strip. Equation 17 illustrates a definition of the strip address range as a function of strip length in the hash table for a 2D case, where:
As discussed above in Section 3.3, in the fixed-rate data case, it was observed that hash construction is less effective if
However, in contrast to the fixed-rate case described above, a least common multiple condition, i.e.,
Finally, with respect to sparsity encoding, in one embodiment, the Variable-Rate Perfect Hasher uses a domain bit array to encode which cells contain no data (as with the aforementioned mask-based embodiment). Alternatively, in the image case, cells having no data are simply encoded in the hash table by entering a data string corresponding to a fully transparent color into the hash table, with a low-resolution color image being used to predict constant-color cells.
3.6 Efficient Random Access of Hashed Data:
Once that sparse variable rate data has been entered into the hash table, as described above, the remaining issues deal with accessing or reading out that data for particular applications. As noted above, one of the many advantages of the Variable-Rate Perfect Hasher is that the data structures created when hashing sparse variable-rate data enable efficient random access to particular data cells or blocks of data cells.
In particular, as illustrated by
In one embodiment, the Variable-Rate Perfect Hasher first checks the mask 370, to determine 710 whether the selected cell has any data. If the mask 370 indicates that the selected cell does not have any data, then the process terminates, and the Variable-Rate Perfect Hasher informs the calling application that the selected cell is undefined (i.e., that it has no data).
On the other hand, assuming that either the mask 370 is not checked 710, or that this check indicates that the selected cell has data, then the Variable-Rate Perfect Hasher determines 720 the corresponding offset table 330 address directly from the address of the selected cell. As described above, this address is determined using a wraparound (i.e., modulo) addressing technique.
Given the offset table 330 address for the selected cell, the Variable-Rate Perfect Hasher then simply retrieves 730 the corresponding offset vector from the offset table. This offset vector is then added to the address of the selected cell, again using a wraparound (i.e., modulo) addressing technique to recover 740 the corresponding hash table 350 address.
Given the hash table 350 address, the Variable-Rate Perfect Hasher then simply retrieves 750 the data string corresponding to the selected cell from the hash table. As noted above, these strings are either self terminating or otherwise include a length such that the Variable-Rate Perfect Hasher knows when to stop reading data for the selected cell. This is an important issue since the data records are variable sized, resulting in the variable length strings described above.
Finally, the Variable-Rate Perfect Hasher then checks 760 to determine whether there are any more selected cells for which data is to be retrieved, and if not, the process terminates. On the other hand, if more cells have been selected 700, then the above described random access processes described above are simply repeated for each selected cell.
The foregoing description of the Variable-Rate Perfect Hasher has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. Further, it should be noted that any or all of the aforementioned alternate embodiments may be used in any combination desired to form additional hybrid embodiments of the Variable-Rate Perfect Hasher. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.
|Brevet citant
|Date de dépôt
|Date de publication
|28 févr. 2008
|4 nov. 2008
|Microsoft Corporation
|Multi-client cluster-based backup and restore
|28 mars 2008
|31 janv. 2012
|International Business Machines Corporation
|Applying various hash methods used in conjunction with a query with a group by clause
|10 déc. 2010
|18 sept. 2012
|Inventec Corporation
|Method for creating a index of the data blocks
|27 oct. 2009
|26 févr. 2013
|Oracle America, Inc.
|Pluperfect hashing
|4 nov. 2010
|14 mai 2013
|International Business Machines Corporation
|Adaptive cell-specific dictionaries for frequency-partitioned multi-dimensional data
|20 avr. 2006
|2 juil. 2013
|Microsoft Corporation
|Sorting large data sets
|19 mai 2012
|3 juin 2014
|International Business Machines Corporation
|Computer interface system
|25 janv. 2008
|8 juil. 2014
|Novell Intellectual Property Holdings, Inc.
|Techniques for reducing storage space and detecting corruption in hash-based application
|17 déc. 2009
|24 févr. 2015
|Business Objects Software Limited
|Optimizing data transfer time on graphics processor units
|13 mars 2013
|17 mars 2015
|The Charles Stark Draper Laboratory, Inc.
|Compressive sensing with local geometric features
|31 déc. 2009
|Bader Aleksey A
|Vectorized parallel collision detection pipeline
|27 oct. 2009
|28 avr. 2011
|Sun Microsystems, Inc.
|Pluperfect hashing
|23 juin 2011
|Varghese Lal Samuel
|Optimizing data transfer time on graphics processor units
|21 juil. 2011
|Siemens Product Lifecycle Management Software Inc.
|Product Lifecycle Management Using a Sparsely Populated Table
|14 juin 2012
|Inventec Corporation
|Method for creating a index of the data blocks
|20 déc. 2012
|Konstantine Iourcha
|Real time on-chip texture decompression using shader processors
|19 déc. 2011
|20 juin 2013
|Franck Diard
|System and Method for Transmitting Graphics Rendered on a Primary Computer to a Secondary Computer
|19 déc. 2012
|19 juin 2014
|Microsoft Corporation
|Runtime transformation of images to match a user interface theme
|13 mars 2013
|10 juil. 2014
|Massachusetts Institute Of Technology
|Compressive sensing with local geometric features
|31 juil. 2013
|5 févr. 2015
|Oracle International Corporation
|Building a hash table using vectorized instructions
|1 aoűt 2013
|5 févr. 2015
|Oracle International Corporation
|Performing an aggregation operation using vectorized instructions
|Classification aux États-Unis
|Classification internationale
|Classification coopérative
|Classification européenne
|21 juin 2007
Owner name: MICROSOFT CORPORATION, WASHINGTON
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HOPPE, HUGUES;REEL/FRAME:019463/0588
Effective date: 20070613
|9 déc. 2014
Owner name: MICROSOFT TECHNOLOGY LICENSING, LLC, WASHINGTON
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MICROSOFT CORPORATION;REEL/FRAME:034542/0001
Effective date: 20141014
|30 janv. 2015
|Maintenance fee reminder mailed
|21 juin 2015
|Lapse for failure to pay maintenance fees
|11 aoűt 2015
|Expired due to failure to pay maintenance fee
Effective date: 20150621


text:
Does Susan Rice think Benjamin Netanyahu is a racist?
Wave of violence sweeping Israel is 'terrorism,' US says
Netanyahu offered vague terms for West Bank withdrawal, former US peace negotiator says
Ex-justice: Oversight 'czar' should also critique attorney general
Low-calorie bread Catch-22
Out and About : Top 10 Things To Do
Oo la la!
Jajo redux
Maccabi Tel Aviv out to avenge recent flops as BSL season tips off
Israel on brink of securing spot in Euro 2016 playoff
Oman cancels Israeli windsurfers' visas
Appreciation: The loss of a renaissance man
Rocket from Gaza lands in southern Israel triggering sirens
Ya'alon urges licensed civilians to carry firearms; Riots reported in Arab towns
Joint List MKs rally in Tel Aviv, Umm al-Fahm
Defense sources fear clip of police shooting suspected terrorist could spark more violence
Abbas working to restore calm in West Bank, Israeli defense sources say
NYC mayor de Blasio to visit Israel, Israeli businessman to foot bill
Edelstein: Romania strong ally in fight against anti-Semitism
Jewish MP in Iran decries 'destruction of mosques in the Muslim World'
Hebrew education – in Harlem
Report: Russian Jewish leader endorses aid to Assad
Sources: US warns governments, bankers Iran sanctions still in place
Khamenei bans Iran from negotiations with US
Sources: US enforcement of Iran arms embargo slipped during nuclear talks
US measure for Iran victims to get paid before sanctions waived inspired by Shurat Hadin
ISIS vs. al-Qaida: Zawahiri says Baghdadi is not the leader of the Muslim world
'ISIS militants blow up ancient Arch of Triumph in Palmyra'
WATCH: Russian warplanes bomb ISIS targets in Syria
'Russia can't claim to fight ISIS terror, while supporting Assad's terror'
Two alleged Hezbollah associates face arms, money laundering charges in New York court
Israel, Iran trade barbs at UN nuclear disarmament panel meeting
Saudi Arabia protests Czech translation of Salman Rushdie's 'Satanic Verses'
Offbeat odor
How to cope with holiday's excess calories and winter's illnesses
Health scan: Israeli physicians slowly warming to medical marijuana
Global space community to reach for the stars
Still too soon to determine production potential of Golan Heights oil
Ness Ziona residents threaten to sue Rehovot for raw sewage flow
Burgeoning alternative fuel firms in Israel grow fivefold in less than three years
IN PICTURES: 1,500 eagles pass over Israel on migration route
Israeli parking app, coming to a university near you
Tech talk: Battle Hacks are back
Facebook pegs Israeli satellite to provide African Internet
Israel to host first international 'Under 30' Forbes Summit
Moody's keeps Israel rating stable
United Airlines to launch non-stop Tel Aviv-San Francisco route
Israel might be heading for the moon
Grapevine: Mission Accomplished
This week in 60 seconds: Terror hits Israel
Grapevine: Labor of love
A faintly Jewish echo
Love, heartbreak, and a brooch – circa 1994
My Word: Succot and the ghosts of intifadas past
Into The Fray: What now?
Looking up to Heaven
Column One: Abbas must be stopped
Parting Shot: Crossing the threshold
Who is a hero?
The diplomacy profession
Coexistence in a cone
2016 Budget: Not just numbers
The good doctor's advice
Courage, rabbis, courage!
Fresh cooking tips from France
Meandering along the Rhine River, soaking up the rich Jewish heritage
Food does grow on trees
A treasure trove of historical posters
Is your dog Jewish?
Ironic Mother Earth
Neighborhood Watch: Regenerating Safed
Cancer Chronicles: Side effects
Feeling uneasy at the moment?
Lonely vigil
מִשִירֵי רָחֵל: זֶמֶר נוּגֶה
אֲנַחְנוּ הַיִשְׂרְאֵלִים
אֲנִי בְּחוֹפֶש, תִסְתַדְרוּ לְבַד
Living in a shoebox
Building health in Rwanda
'The Sabbath is on Saturday not Sunday'
Born to dance
Bereshit: The Subatomic and Atomic
America wants out and let the chips fall where they may!
Computer Generated Spirituality
The Tower and the Sword
Do Not Fear - Do Laundry!
Inauguration of the Masonic Forest Square in Jerusalem
Free Schach Distribution in KKL-JNF Forests
Remembering the Victims of 9/11
600 Holocaust Survivors Enjoy Touring with KKL-JNF
greenXchange at EXPO Milano
First Tree after Shmita Year Planted by Bavarian Agriculture Minister
Prime Minister of Lithuania Plants Tree in Jerusalem
KKL-JNF International Expo Mission to Milan
An Ecological Festival at the Shafir Winter Pond
KKL-JNF Global Landscapes Seminar at Expo 2015
New Bio-filters Purify Surface Runoff Water for Reuse
Future Tour Guides Discover the Negev with KKL-JNF
Got Water Problems?
$100 Million JNF Boruchin Israel Education Advocacy Center Opens
JNF Canada Pays Tribute to the Honourable John Baird
From Sunny Israel to Cold Canada
Renewable Energies for the Future in the Arava
LDA Conference: Science and Technology for Forests
The Negev Conference on Agricultural Research and Development
Arava Open Day: Food Security for Israel and the Entire World
Melinda and Chelsea: The Inspiring Story of Aliyah Across the Ages
An Olah Reports From Nepal
How One Oleh is Helping to Transform the Way People Drink Water
From Think Tank to Environmental Consultant
Why People Love Volunteering in Israel
How Natalie Edwards Built a Successful Career in Israel's Startup Industry
5 Tips to Land a Job in Israel
Starting Your Own Business in Israel: Real Life Examples
Where Are They Now? The Olim of the July 2014 Charter Flight
36 Hours in Southern Israel
Food Shopping In Israel
How Women Can Have it All in Israel
Why Retirees are Thriving in Israel
Thanks to Aliyah video
6 Frequently Asked Questions about Israeli Healthcare
Starting Over in Israel
Spotted on Social: Moshe Somers' Activity List
Sam Eisenberg: From Nativ to Aliyah
WATCH: Why Olim #LiveLoveIsrael
5 Ways that Olim Kick Back
WATCH: Highlights of 221 Olim Landing on the July 2015 Charter Flight
"WATCH: Highlights of 232 Olim Landing on the August 2015 Charter Flight"
Make yourself at home… in Israel
10.10.2015 | 27 Tishri, 5776
Promising trend of prosecution for environmental crimes, officials say
Yazidi boy recovering from surgery in Israel, father worried about family in Iraq
Portions of the Western Wall may be facing problematic erosion
Israeli math team take top prize for the first time at International Mathematics Competition
Israeli Ebola researcher unique in learning how some victims survive
State and local council to replace asbestos roofs in the line of fire from Gaza
Environment Ministry says oil shale pilot project in Shfela is environmentally destructive
MK Henin: Immediate action is needed to curb pollution levels in the Haifa Bay
'Export of Leviathan gas to Turkey unlikely without improvement in political ties'
NGOs to panel: Public must benefit more from profits on natural resources
Ministerial committee approves new land, sea gas reception terminals
Exploratory oil drilling in Golan Heights approved
04/18/2012 04:23
Psychology building in Bar-Ilan University 390.
(photo credit:Avishai Teicher via the PikiWiki - Israel free ima)
Research expenditures at the universities granted by outside sources and
intra-university grants – excluding funding from the universities' budgets –
totaled NIS 1.5 billion shekels during the last recorded 2008-2009 academic
year, according to the Central Bureau of Statistics.The CBS relied on
data from the Science and Technology Minister's National Council for Research
and Development.Announced on Tuesday, the figure rose over 5 percent
from the previous year, in which research using "special financing" reached NIS
1.45 billion. The external funding constituted 13% of all civilian R&D in
the country in 2008-2009.According to the ministry, 63% of the funds
were allocated for research in the fields of mathematics, natural sciences and
medicine; 16% for social sciences and law; 16% for engineering and architecture;
3% for agriculture; and the remainder in undefined fields.Between 2007
and 2009, slight changes occurred in the allocation of funds. Biological
research declined from 30% to 27%, physical sciences rose from 18% to 20%; and
engineering and architecture rose from 14% to 16%. The medical field remained
unchanged.Almost 60% of the special funding originated in Israel, with
the rest from abroad.Israeli funding was especially large in the fields
of humanities and law, social sciences and agriculture. The public sector paid
for 36% of special funding. While 30% originates in foundation money, the
business sector provided only 9%. The natural sciences recorded a relatively
large share of public funding from abroad.National Research and
Development Council chairman Prof. Yitzhak Ben-Yisrael said that the high figure
for funding from abroad shows the "quality, competitive ability and the
international nature of university research in Israel." He added that 40% of the
university research is collaborative with foreign institutions. "The data show
that Israeli universities network well with those abroad," he said.Prof.
Ehud Gazit, the ministry's new chief scientist, said that Israeli research
institutions are well known for their ability to attract competitive funding
among thousands of universities around the world. Recently, four Israeli
universities have been ranked among the 50 best in getting competitive financing
for their research, Gazit said.The Hebrew University of Jerusalem has
the best record, receiving NIS 397 million for research in 2009 from special
funding. Tel Aviv University's funds totaled NIS 318 m. The Weizmann Institute
of Science in Rehovot received NIS 243 m.from abroad, followed by
Haifa's Technion-Institute of Technology with NIS 225 m.and Ben-Gurion
University of the Negev in Beersheba with NIS 192 m. Bar-Ilan University in
Ramat Gan came next with NIS 88 m. and the University of Haifa garnered
NIS 59 m.
Your comment must be approved by a moderator before being published on JPost.com.
Disqus users can post comments automatically.
Comments must adhere to our Talkback policy. If you believe that a comment has breached the Talkback policy, please press the flag icon to bring it to the attention of our moderation team.
Sign up for our newsletter
Please insert a valid email address
By signing up to The Jpost mailing list, I hereby

subset: commoncrawl


text:
Applications are invited from the eligible candidates for admission into MBA Program for the Academic Year 2013 – 2015 at National Institute of Technology Karnataka (NITK), Surathkal. Eligibility: Candidates must have bachelors degree in any discipline from recognized university with not less than 60% marks (or CGPA of at least 6.5 in the 0-10 scale grading … Read more
Search Results for : cutoff rank for nitk 2013
Karnataka National Institute of Technology (Technology) 2014 – 15 Ph.D. Applications are invited for admissions. Details … * Ph.D. Specializations: Civil Engineering and Applied Mechanics & Hydraulics, Mechanical Engineering, Electrical Engineering, Electronics & Communication Engineering, Chemical Engineering, Metallurgical & Materials Engineering, Mining Engineering, Physics, Chemistry, Humanities-Social Sciences & Management, Mathematics & Computational Sciences, IT, Computer … Read more
Indian Institutes of Science Education and Research (IISERs) at Kolkata, Bhopal, Mohali, Pune and Thiruvananthapuram invites applications from the eligible candidates for admission into 5 Year BS-MS Dual Degree Program for the starting from the Academic Session August 2013. Eligibility: Candidates satisfying at least one of the following three criteria may apply (KVPY) Science Stream: … Read more
Applications are invited for admission into its MBA Programme for the session 2014 at National Institute of Technology, Karnataka: Eligibility Criteria The candidate must possess a Bachelors Degree from any recognised university with minimum of 60% of marks 0r 6.5 score in CGPA. Candidates will be finally selected taking account as CAT 2013 score, group discussion, … Read more
Suratkal National Institute of Technology Karnataka (Knit-K) has issued to the MBA program in 2015. Details ……. 2015 MBA program Number of seats: 64 Duration: 2 years. Candidates should be 50 per cent marks in any degree. CAT / GMAT qualify. Option: CAT / GMAT score is based on a select group discussion and … Read more
Suratkallo Karnataka National Institute of Technology (Technology) Applications are invited for admission to the PhD program. Details ……….. PhD program in December 2014 Number of seats: 54 Sections: Applied Mechanics and Hydraulic, Electrical, Metallurgical and Materials, Mining, Mechanical, Chemical, Civil, Electronics and Communication, Computer Science and Engineering, Chemistry, mathematics, Physics, Humanities and Social Sciences. Duration: … Read more
AP ICET 2015 Counselling Dates – Rank Wise List (https://apicet.nic.in) Rank Wise ICET 2015 Counseling Schedule – Andhra Pradesh AP ICET 2015 Notification has been released for Certificate Verification and Online Option to be exercised for Web Based Counseling. Andhra University has released Rank Wise counselling notification to get admission into MBA/MCA courses for the … Read more
TS ICET Rank Card 2015 – MCA and MBA Entrance Exam (http://tsicet.org/) TSICET-2015 is the first Telangana State Integrated Common Entrance Test (TSICET) for admission into M.B.A. and M.C.A. courses of all the Universities in Telangana State and their affiliated colleges. This test is being conducted by Kakatiya University, Warangal on behalf of Telangana State … Read more
AP ICET 2015 Web Based Counselling (https://apicet.nic.in) Rank Wise ICET 2015 Web Based Counselling – Andhra Pradesh AP ICET 2015 Notification has been released for Certificate Verification and Online Option to be exercised for Web Based Counseling. Andhra University has released Rank Wise counselling notification to get admission into MBA/MCA courses for the academic year … Read more
OU Distance Mode Counseling For B.Ed II&III Phase Of Counselling. B.Ed. (Distance Mode) 2nd & Final Phase of Counselling The Second & Final phase of counselling for admission into B.Ed. (DM) will be conducted on 08.03.2014 at the office of the Director, Directorate of Admissions, Osmania University, Hyderabad to fill up the existing … Read more


text:
Soldiers' Angels
Rating: 4.84 stars 704 reviews
Issues: Disaster Aid, Human Services, Veterans
Location: 2700 NE Loop 410, Suite 310 San Antonio TX 78217 USA
Target demographics: the men and women of the United States Army, Marines, Navy, Air Force, Coast Guard, their families, and Veterans of all eras.
Geographic areas served: the United States and around the world
Programs: - Adopt a Soldier: Individualized support throughout deployment - Angel Bakers: Homemade treats for the deployed - Chaplain Support Team: Help chaplains support the troops - Ladies of Liberty: Extra TLC for deployed females - Letter Writing Team: Personal letters for the deployed - SA Germany: Supporting medevac'd wounded/ill and medical staff at Landstuhl - Valour-IT: Providing adaptive laptops for the severely wounded or injured - VA Hospital Support - Living Legends: Comforting the loved ones left behind when a warrior falls on the battlefield - Operation Top Knot: Handmade gifts & virtual baby showers - Adopt-A-Family: Holiday adoption program to support a family's holiday needs - Women of Valor: Support to female caregivers of Post 9-11 wounded, ill and injured service members. - Sewing Team: Handmade blankets, scarves and pillowcases - Cards Plus Team: Extra TLC for soldiers and families
Filter Reviews by Role
Promote This Nonprofit
GreatNonprofits badges allow you to raise awareness of your favorite nonprofits on your own web sites!
Community Reviews
2 people found this review helpful
I am currently deployed out in the persian gulf and this organization has been very generous and supportive to me and my ship. I really appreciate the individuals from this organization that have sent care packages and letters of support. It's hard being out here in the sand box but these letters from home really reminds us why we choose to serve.
More Feedback
I love having a angel to talk to when things are getting me down. They listen and give great input when need. They will always be my angel. My husband loved getting father day cards. Made him feel important and not just the person in the background.
More Feedback
When my husband was injured soldier's angels donated some clothes to him. I never thought about what was on that shirt. It's been 5 years now and I recently found soldier's angels when we didn't know how we were going to survive. His injuries had progressed to where he is unable to work and some days unable to get out of bed. Since finding this organization, I have found support that I have desperately needed. My husband has realized that he is not alone. We have become a stronger couple and before we were almost to a point where we were ready to give up. This organization has given us both hope. Where all was lost a few months ago. I am so very thankful that I found them.
More Feedback
My husband was adopted by Soldier's Angels while he was in Iraq. Since he was injured, the Soldier's Angels have adopted me on holidays such as Mother's Day, and my husband during Father's Day. We have received wonderful letters, and even a few gifts. These Angels are selfless and have really touched our hearts.
More Feedback
Love soldiers angels. It is nice to know we are not forgotten.
More Feedback
thank you Soldiers' Angels for giving me some attention and care from home while on deployment. The smallest things that help us. ~Jason Halstead
More Feedback
How would you describe the help you got from this organization?
How likely are you to recommend this organization to a friend?
How do you feel you were treated by this organization?
Very Well
When was your last experience with this nonprofit?
These folks are angels, no doubt about it. I have been blessed to receive their help, and their beautiful cards and letters, as I prepare for the birth of my first child. My husband is deployed again, and things are stressful. Having the blessings that these folks provide, and the encouragement of their beautiful letters, has made a huge difference. I will return the favor and become a volunteer once my husband is home and we are past the initial burden of a newborn. I cannot thank these folks enough. They are truly blessed angels!
More Feedback
This group really made me feel appreciated!
SPC Dues
More Feedback
I love soldier angels through 3 deployments they have kept me encouraged and motivated through letters and packages. Thank you for all that you do for us.
More Feedback
2 people found this review helpful
Soldiers' angels is an great organization. Since I've deployed they have provided great things to me and fellow soldiers. I am thankful for their support.


text:
'Simpsons'' David Silverman Speaks
With The Simpsons Movie hitting DVD, Russell Bekins took an opportunity to chat with director David Silverman about his long history with the TV series, as well as its huge jump to the big screen.
With The Simpsons Movie hitting DVD, Russell Bekins took an opportunity to chat with director David Silverman about his long history with the TV series, as well as its huge jump to the big screen.
4Kids Ent., Inc. announced today that it has appointed Barry Stagg as SVP, Corporate Communications. In his new position, Stagg will be responsible for implementing a global communications program to expand the awareness of 4Kids' current properties and operations, as well as new brands and business ventures.
Molly Chase has been named VP and exec producer for Cartoon Network New Media. In her new role, Chase will oversee several Cartoon Network New Media departments including the design studio, technology group, game studio and the production team, and will be responsible for directing all aspects of production for CartoonNetwork.com, Awesomehouseparty.com and ToonamiJetstream.com.
Upon his retirement from UCLA, Professor Dan McLaughlin speaks with student Chris Mais about his 50-year career as an independent animator and educator of the next generation of filmmakers.
With the feature animation industry booming in India, Lisa Goldman reports on the opportunities and challenges presented by an immense and diverse audience.
Dan Lin, who is overseeing JUSTICE LEAGUE, has left his SVP of Production post at Warner Bros. to form his own production unit on the lot, report the trades. Lin will officially move over to Lin Pictures starting Jan. 1. The deal will see Lin producing films for Warners exclusively for the first three years of his contract, as well as remaining the shepherd on projects he already has in development and in production under his current SVP role.
Pokemon USA, Inc. has announced that Akira Chiba, who has led the American branch of the company since 2002, will resign at the end of the year. Chiba joined Pokemon USA when the company's New York office was established -- the brand's first corporate headquarters outside of Japan and helped to re-establish Pokemon as a successful global brand.
Russell Bekins takes in the animation family reunion at I Castelli Animati, a festival where filmmakers come to connect with colleagues in a laid-back atmosphere.
Sesame Workshop, the nonprofit educational organization behind SESAME STREET and other educational programs, has announced the addition of Aura Kenny Dunn to its staff as Assistant VP, Government Affairs. In this capacity, Dunn will manage government relations efforts and advance Sesame Workshop's visibility in federal policy and funding arenas to promote education and well-being for children around the globe. She will report to Myung Kang-Huneke, VP, General Counsel.
Jacquelyn Martino, a renowned researcher and graduate from MIT, was recently selected to chair SIGGRAPH 2008, the 35th International Conference and Exhibition on Computer Graphics and Interactive Techniques. With the theme Evolve, SIGGRAPH returns to the Los Angeles Convention Center. The conference will take place Aug. 11-15, with the exhibition occurring Aug. 12-14.
Sue Troyan has joined Brickyard VFX's Santa Monica facility as exec producer after departing Method Studios as head of production.
"I have known and worked with Sue on and off for over 15 years, and she has a deep knowledge of the visual effects process and a fantastic reputationamong top commercial production companies and advertising agencies," said Steve Michaels, managing partner, Brickyard VFX. "We're really excited to have her on board."
Entertainment Rights (ER) Plc, the U.K.-based media group specializing in the ownership of children's and family programming, characters and brands, has announced the appointment of Adam Selly as Head of Sales (excluding the U.S., Canada and Japan). In the newly created position, Selly will be responsible for generating and maximizing revenue across the ER group's entire television and home entertainment businesses, exploiting opportunities within existing successful markets and identifying new revenue streams in emerging markets.
Jon Hofferman surveyed a host of filmmakers to find out what we can expect from them in the near and distant future.
As part of an effort to accelerate the growth of its presence in the Asia-Pacific markets, Twentieth Century Fox has announced the appointment of Grant Kahn to VP of International Licensing. Kahn has more than 13 years of international business development experience, representing U.S. companies in strategic planning, marketing and selling to Asia-Pacific countries.
Veteran animation executive Sam Register (BEN 10, TEEN TITANS, HI HI PUFFY AMIYUMI) has entered into a multi-property development and production deal with Warner Bros. Animation. Register will also continue to work with sister company Cartoon Network through a first-look development deal that was announced last fall.
Leading children's entertainment producer Animation Collective today announced it has appointed Doug MacLennan COO. Mr. MacLennan previously served as VP of Finance for the company, where he oversaw the budgeting and financing of its co-productions. In his new role, MacLennan will be responsible for leading Animation Collective's corporate strategy and multi-platform initiatives.
MacLennan will report directly to Larry Schwarz, Animation Collective's founder and CEO, and replaces Michael Gold, who left the company to pursue an educational software venture.
Mark Miller has replaced Carl Stork as CEO of Digital Domain. The former ILM exec will continue as president and retain his seat on the board of directors. Stork will now serve as vice chairman of the board.
"Mark Miller has two decades of experience in the visual effects industry," said Stork, "and he has demonstrated effective leadership of the company.It's great to recognize Mark's contribution with this promotion to CEO. I certainly plan to remain an active voice in the direction of this company, and I look forward to my new role as vice chairman."
Scholastic Media, the entertainment and media division of children's publishing, education and media company Scholastic, has hired Daisy Kline as Director of Marketing & Brand Management, reporting to Leslye Schaefer, SVP, Marketing and Consumer Products. Kline will be responsible for overseeing all marketing initiatives and brand strategies for Scholastic Media properties, including CLIFFORD THE BIG RED DOG, GOOSEBUMPS, WORDGIRL, I SPY, THE MAGIC SCHOOL BUS, and DRAGON for the multimedia and consumer products arena.
DreamWorks Animation SKG, Inc. today announced that senior team members Bill Damaschke and John Batter have been promoted to Co-Presidents of Production for Feature Animation, with Damaschke also being appointed to the newly created position of President of Live Theatrical.
Viacom's MTV Networks Argentina has appointed Juan Frontini Creative Director of MTV Latin America. The appointment is part of MTV Networks Latin America's strategy to regionalize and expand its programming and production operations locally. Based in Buenos Aires, Frontini will report to Sean Saylor, Vice President of Creative for MTV and VH1 Latin America, based in Miami Florida.
Veteran programmer Lauren Corrao has been named president, original programming and development for Comedy Central. Corrao, who is based in the network's offices in Los Angeles and was formerly exec VP, original programming and development, will continue to report to Doug Herzog, president, MTV Networks Entertainment Group.
Nickelodeon/MTVN Kids and Family Group has expanded Nicktoons Network GM Keith Dawkins' position to SVP, Nickelodeon Programming Partnerships. In this new role, Dawkins will be responsible for forging new creative partnerships and co-productions with non-traditional programming partners, while overseeing the international and domestic acquisitions of series, films and short-form programming for both Nickelodeon and Nicktoons Network. Dawkins reports to Marjorie Cohn, EVP Development and Original Programming, Nickelodeon/MTVN Kids and Family Group.
Indias Pune-based Anirights Infomedia has added two new vice presidents as part of an expansion spree, reports ANIMATION XPRESS. Praful Gade joins the company as VP, 3D Animation Pipeline and Shamboo Phalke is the new VP, 2D Animation Pipeline.
During his 20-year career, Gade has worked in various capacities, leading teams at Prasad Studios and Chromatic Technologies, among others. Prior to joining Anirights, he was Chief of Operations at Delhi-based Escotoonz.
The Visual Effects Society (VES) has elected a new board of directors for the upcoming year. The new members will take office at the Jan. 9, 2008, board meeting.
"This group of people represents an amazing array of talent and diversity," said Jeff Okun, outgoing chair. "They range from heads of companies and model makers to Academy Award-winning visual effects supervisors and producers.VES has always attracted the most talented, experience and knowledgeable individuals to it and we will surely be in good hands with group talented individuals at the helm."


text:
Select Local Merchants
Iron Hill BreweryRead MoreIron Hill Brewery offers a laid-back atmosphere and tasty American classics. Stay clear of unhealthy cravings at Iron Hill Brewery, a local restaurant that serves both low-fat and healthy eats. Find time to peruse the wine list here — Iron Hill Brewery offers a variety of drink options. The whole family can enjoy a meal at Iron Hill Brewery with its kid-friendly fare. Having a lot of friends can be complicated, but Iron Hill Brewery makes it easy to please everyone. Enjoy the luxury of eating a delicious meal outside at Iron Hill Brewery. Good luck spotting a suit and tie at Iron Hill Brewery — casually-dressed diners are the norm here. You can also grab your food to go. Iron Hill Brewery's diners can safely park on the street, as well as in a nearby lot. Make use of the safe and efficient bike parking at Iron Hill Brewery. A mid-priced establishment, Iron Hill Brewery offers meals that typically cost about $30 or less.30 E State StMedia, PA US
Manayunk Brewery and RestaurantRead MoreManayunk Brewery and Restaurant is a relaxed restaurant with an elegant decor and classic American dishes. No need to miss out on Manayunk Brewery and Restaurant just because you are avoiding fat or gluten. The restaurant has plenty of options that can accommodate your dietary needs. Those who enjoy a drink or two with dinner are advised to take advantage of Manayunk Brewery and Restaurant's BYOB policy. Order a bottle for the table if you like — Manayunk Brewery and Restaurant has a full bar stocked with the best wine, beer, and more. Save money on a sitter — kids are welcome to join the table at Manayunk Brewery and Restaurant. Have a big celebration coming up? Consider the private room at Manayunk Brewery and Restaurant, perfect for large groups of revelers. Patio tables and chairs are ready for Manayunk Brewery and Restaurant diners who prefer their meals al fresco. Wear what you like when you dine at Manayunk Brewery and Restaurant — the restaurant has a chill vibe just right for casual dining. If you're in a hurry, place an order for pickup instead. The restaurant also offers catering if you want to bring the flavors of Manayunk Brewery and Restaurant to your next party or event. For diners who choose to drive to the restaurant, parking is readily available — the nearby lot offers optional valet, and street parking is also accessible. Typical diners should plan to spend about $30 per person on Manayunk Brewery and Restaurant's moderately priced fare. Breakfast, lunch, and dinner are all served at Manayunk Brewery and Restaurant, so come by whenever it fits your schedule.4120 Main StPhiladelphia, PA US
Dock Street BreweryRead MoreDock Street Brewery is a pub and restaurant located in Philadelphia and has become a local favorite for its quality beer options, but almost equally importantly its delicious pizza. The brewery was founded in 1985 and was the first microbrewery in Philadelphia and became one of the leading breweries in the country. Several award winning beers have been produced at Dock Street Brewery including the Dock Street Amber beer, Bohemian Pilsner and more. There are few breweries in the area that take as much pride in their beer as they do with their food, and for hungry patrons there are several choices available including vegan and vegetarian pizzas and several ingredient options for pizzas, calzones, breakfast pizzas and frittatas, and more. There are also some of the most unique and unusual pizzas that you can find anywhere at Dock Street including the Fig Jam Pizza and the Bacon and Onion Flammenkuche.701 S 50th StPhiladelphia, PA US
Yards Brewing Co.Read MoreBLT, club, veggie, and more...Yards Brewing Co. serves sandwiches too tasty to pass up. Put the diet on pause when you visit Yards Brewing Co. — there are no low-fat menu items. Yards Brewing Co. is completely informal — dress as you see fit (and are most comfortable). Guests take to street parking at Yards Brewing Co.'s N Delaware Ave spot. Expect to spend less than $15 per person at Yards Brewing Co. Don't leave the dollar bills at home — you'll need cash at Yards Brewing Co. The menu at Yards Brewing Co. includes breakfast, lunch, and dinner — stop by for your favorite meal.901 N Delaware AvePhiladelphia, PA US
Earth Bread + BreweryRead MoreOnly King Arthur's flour is good enough for the bread bakers at Philadelphia's own Earth Bread & Brewery. Not only is the bread undeniably amazing, but so are the creative toppings. Imagine a flatbread topped with roasted garlic, pine nuts, pumpkin and sesame seeds, mozzarella, and red pepper flakes. Yum. The mozzarella is also freshly prepared daily in the Earth Bread & Brewery kitchen. Along with their breads, Earth Bread & Brewery serves impressive salads, a cheese plate, hummus sampler, dip of the day, and housemade sweets. Round out the meal with an extensive list of wine and sipping spirits.7136 Germantown AvePhiladelphia, PA US
Brew Your Own BeerRead MoreLooking for a great way to enjoy some quality family time? Grab some hobby supplies from Havertown's Brew Your Own Beer and create a family project. If you're commuting by car, you will be happy to know that Brew Your Own Beer is located near a number of parking options. Bikers can store their bikes safely while they enjoy a meal at Brew Your Own Beer. So what's your interest? Explore that and more at Brew Your Own Beer in Havertown.2026 Darby RdHavertown, PA US


text:
Related Searches: Flight helmet, catcher's helmet, vintage helmet, pilot helmet
11 Results for Captain America Helmet - For Sale Classifieds
This is a preowned Child's The Avengers Captain America Costume Accessory Shield and helmet. The shield is in played with condition.1 month ago on ebay.com
Powered by Frooition Pro in titles & description MarMarvel Captain America Super Soldier Gear Battle Helmet Product Specifications:Manufacturers Suggested Age: 5 Years and Up Textile Material: 100% Polypropylene1 month ago on ebay.com
Top shield has a hard time closing-it shoots out 4 nerf darts!! Helmet lights up red and vehicle is missing parts!1 month ago on ebay.com
CAPTAIN AMERICA MOVIE PROP HELMET SIGNED BY THE LIVING LEGEND STAN LEE CREATOR OF MARVELS AND SPIDERMAN ITEM HAS HOLOGRAM TAMPER THE HELMET WITH MATCHING NUMBERS ON COA CARD FROM PSA/ DNA Posted with eBay Mobile1 month ago on ebay.com
This Hi Res Movie Poster has been printed on a premium vinyl using archival quality inks. We can custom print any image image and custom size as well. Feel free to contact me with any questions. If you are intereste1 month ago on ebay.com
trademark of a handcrafted Sideshow Collectibles product. Featuring real fabric costume detail and switch-out helmeted or unhelmeted portraits, the Captain America Premium Format Figure is an outstanding addition to any Marvel1 month ago on ebay.com
PACKS FOR*BATMAN* FLASH GORDON* CAPTAIN AMERICA* SGT. FURY* THE PHANTOM* SUPERMAN* AQUAMAN* STEVE CANYON* THE LONE RANGER * 1 PAGE Features The BATMAN UTILITY BELT, HELMET & EQUIPMENT SET* 1965 IDEAL TOY CATALOG COVER PAGE1 month ago on ebay.com
Loose lot of 9 1980's Vintage Kenner DC Marvel figure lot Secret Wars Super Powers etcRobin, Freeze (broken helmet), Penguin (Umbrella Parts), Luthor,Doctor Doom, Spider-man, Captain America, Magneto, Doctor1 month ago on ebay.com


text:
Welcome to the Literary Encyclopedia
"Note how democratic is the earth. Today a respectable married couple sleeps on the same bit of ground that yesterday suffered a couple living in sin. Tomorrow a priest may sleep there, then a murderer, then a blacksmith, then a poet; and, like shipwrecked persons whose lifeboat has delivered them safely to shore, they will bless this bit of ground, for it gives them the illusion of security.."


text:
Out-Of-School Special
Come enjoy a movie at the library! Covered drinks and treats are welcomed. No registration required.
Come enjoy a movie at the library! Covered drinks and treats are welcomed. No registration required.
Baby Time is a 6 week program for children newborn-18 months and their caregiver. It is held from 9:00-9:30. The program helps foster an appreciation for literacy and focuses on the loving relationship between parent and child. To register, please call 647-0328.
Toddler Time is a 6 week program for children ages 19 months to 2 years and their caregiver. It is held from 10:00-10:30 a.m. The program helps foster an appreciation for literacy, learning, and social skills. To register, please call 647-0328.
Search our catalog for books, movies and more.
205 West Chestnut
Canton, IL 61520-2499
309-647-0328 (phone) - 309-647-8117 (fax)
Monday - Thursday: 9 a.m. to 8 p.m.
(Year round)
Friday: 9 a.m. to 6 p.m.
(Year round)
Saturday: 9 a.m. to 4 p.m.
(Summer hours: 9 a.m. to 1 p.m.)
Sunday: Closed
Ms. Catherine is getting ready for all her fall programs. She has a variety of opportunities for you and your child to enjoy this season. Come in and take a look at all our program flyers to see what will work for you. Some programs need registration, so sign up soon.
The library offers free Outreach Services to homebound residents within Canton city limits. We deliver to nursing homes, retirement communities, and to anyone who can't visit us personally. If you or someone you know is interested in this service, please call 647-0328 to get signed up.
As of June 1, 2015, Parlin-Ingersoll Public Library can now notarize documents for the public. We have three staff members who have trained to be a Notary Public. We hope this service will give our patrons more options for completing their paperwork needs. Appointments are recommended. For more info, please call 647-0328.


text:
Things to see and do - Mustafapasa
Leaving for Turkey
Where to sleep?
Mustafapasa Hotel tips
Gul Konakları - Sinasos - Special Category from36 €Book
Jerveni Cave Hotel from65 €Book
Osiana Hotel from40 €Book
Mustafapasa Travel guide
Mustafapasa : Michelin's recommendations
Strung out along a cliff, the large village of Mustafapasa is home to numerous beautiful stone houses with sculpted façades, built by the Greeks who lived here until 1923. A good example of the town's past prosperity, the Church of St Constantine and St Helen dominates the village centre, and is adorned with a pediment painted with polychrome grapes. Near the square, a 14C medersa (which now houses a carpet shop) has retained its elegant sculpted doorway. Finally, make sure you have time for a cup of tea at the Old Greek House, a superb house dating from the 19C.
Hotels Mustafapasa
Helios Cave Hotel
Davutlu Mevkii Kılıçarslan Sk 13 Ürgüp Nevşehir (Sinasos) TR - 50420 Urgup
Prix Prices from : 55 €
Offering a barbecue and views of the mountains, Helios Cave Hotel is situated in Urgup. Guests can enjoy the on-site restaurant. All rooms have a flat-screen TV with cable channels. Certain units include a seating area where you can relax. A terrace..
Jerveni Cave Hotel
Yukarı Mah. Zafer Cad. No:17 Kopru Yanı Mustafapaşa Kasabası TR - 50104 Urgup
Situated in the old Greek village Mustafapasa, Jerveni Cave Hotel offers authentic rooms with modern amenities and free Wi-Fi. There is a small museum in the hotel and a restaurant serving traditional cuisine. Featuring stone walls, the rooms of Jer..
Cave Art Hotel Cappadocia
Yukari Mah. Manastir Sok. No:11 Mustafapasa Urgup TR - 50400 Urgup
Prix Prices from : 130 €
Nestled among the valleys, churches and fairy chimneys of the town, Cave Art Cappadocia is built in a restored stone structure protecting its origins. It offers a terrace restaurant with panoramic views over the town and soundproofed rooms. Cave Art..