精华内容
下载资源
问答
  • 内部存储空间 手机存储空间 sd卡

    千次阅读 2015-10-16 15:49:08
    有些手机(如MTK平台)分内部存储空间和手机存储空间,据说内部存储空间只是给装软件用的,而手机存储空间类似内置的SD卡,这样分经常导致安装软件时,明明有空间,但是还是装不下。请问为什么要这样分呢?有什么...

    有些手机(如MTK平台)分内部存储空间和手机存储空间,据说内部存储空间只是给装软件用的,而手机存储空间类似内置的SD卡,这样分经常导致安装软件时,明明有空间,但是还是装不下。请问为什么要这样分呢?有什么好处和坏处?而其他平台手机大多都是只分为一大块存储空间,如三星索尼等,没有内部存储空间和手机存储空间之分,安装软件和放照片都OK。


    早期的安卓系统设计了两块用户可用的存储空间,即:

    • /data分区:所谓“内部存储空间”,可以装app,也可以保存app的数据,但用户不能用它保存自己的文件(比如照片/视频/音乐等)
    • /sdcard分区:加载一张可移除的SD存储卡,可以装app,可以保存app的数据,也可以供用户保存自己的文件
    后来有一些厂商开始在手机里内置一块EMMC存储卡,分成若干分区,/data分区和/sdcard分区都是从上面划分出来的,这时/sdcard分区会显示成“手机存储空间”,但这两个分区的作用没有变化。为了继续支持SD卡,有的厂商会扩展安卓系统,比如索尼增加了一个/ext_card分区用于加载SD卡。

    再后来有些厂商开始觉悟,做出了合并/data分区和/sdcard分区的方案,即只从EMMC卡上分一个/data分区,然后它的某个子目录虚拟成/sdcard分区,这样的话/data和/sdcard共享空间,可供保存文件的存储空间更大了。

    安卓自版本4.2开始,提供了这种虚拟分区的内置支持,相信会有越来越多的手机支持这个特性。



    安卓系统分区介绍:

    英文原文:Android Partitions Explained: boot, system, recovery, data, cache & misc  地址:

    安卓手机和平板一般包括以下标准内部分区:
    • /boot
    • /system
    • /recovery
    • /data
    • /cache
    • /misc

    另外还与SD卡分区:

    • /sdcard
    • /sd-ext

    现中英文对照如下:

    注意,只有/sdcard在所有安卓设备豆油。其它只在部分设备中有。下面看一下各个分区的内容和作用。

    Note that only /sdcard is found in all Android devices and the rest are present only in select devices. Let’s now take a look at the purpose and contents of each of these partitions.

    /boot

    正如名字所代表的意思(注:boot的意思是启动),这个分区使手机可以启动。它包括了内核(kerne)和ramdisk两部分。如果没有这个分区,手机通常无法启动到安卓系统。只有必要的时候,才去通过Recovery软件擦除(format)这个分区,一旦擦除,设备只有再从新安装一个新的boot分区,可以通过安装一个包含boot分区的ROM来实现,否则无法启动安卓系统。

    This is the partition that enables the phone to boot, as the name suggests. It includes the kernel and the ramdisk. Without this partition, the device will simply not be able to boot. Wiping this partition from recovery should only be done if absolutely required and once done, the device must NOT be rebooted before installing a new one, which can be done by installing a ROM that includes a /boot partition.

    /system

    这个分区基本包含了整个安卓操作系统,除了内核(kerne)和ramdisk。包括安卓用户界面、和所有预装的系统应用程序。擦除这个分区,会删除真个安卓系统,但不会导致不能启动。你可以通过进入Recovery程序或者bootloader程序中,安装一个新ROM,也就是新安卓系统。

    This partition basically contains the entire operating system, other than the kernel and the ramdisk. This includes the Android user interface as well as all the system applications that come pre-installed on the device. Wiping this partition will remove Android from the device without rendering it unbootable, and you will still be able to put the phone into recovery or bootloader mode to install a new ROM.

    /recovery

    这个分区可以认为是一个boot分区的替代品,可以是你的手机进入Recovery程序,进行高级恢复或安卓系统维护工作。要更详细的了解这个分区,请参考CWM使用指南。

    The recovery partition can be considered as an alternative boot partition that lets you boot the device into a recovery console for performing advanced recovery and maintenance operations on it. To learn more about this partition and its contents, see the ‘About Android Recovery’ section of our guide to ClockworkMod recovery

    /data

    这个分区也叫用户数据区,包含了用户的数据:联系人、短信、设置、用户安装的程序。擦除这个分区,本质上等同于手机恢复出厂设置,也就是手机系统第一次启动时的状态,或者是最后一次安装官方或第三方ROM后的状态。在Recovery程序中进行的“data/factory reset ”操作就是在擦除这个分区。

    Also called userdata, the data partition contains the user’s data – this is where your contacts, messages, settings and apps that you have installed go. Wiping this partition essentially performs a factory reset on your device, restoring it to the way it was when you first booted it, or the way it was after the last official or custom ROM installation. When you perform a wipe data/factory reset from recovery, it is this partition that you are wiping.

    /cache

    这个分区是安卓系统缓存区,保存系统最常访问的数据和应用程序。擦除这个分区,不会影响个人数据,只是删除了这个分区中已经保存的缓存内容,缓存内容会在后续手机使用过程中重新自动生成。

    This is the partition where Android stores frequently accessed data and app components. Wiping the cache doesn’t effect your personal data but simply gets rid of the existing data there, which gets automatically rebuilt as you continue using the device.

    /misc

    这个分区包括了一些杂项内容:比如一些系统设置和系统功能启用禁用设置。这些设置包括CID(运营商或区域识别码)、USB设置和一些硬件设置等等。这是一个很重要的分区,如果此分区损坏或者部分数据丢失,手机的一些特定功能可能不能正常工作。

    This partition contains miscellaneous system settings in form of on/off switches. These settings may include CID (Carrier or Region ID), USB configuration and certain hardware settings etc. This is an important partition and if it is corrupt or missing, several of the device’s features will will not function normally.

    /sdcard

    这个分区不是设备系统存储空间,是SD卡空间。从使用上讲,这个是你自己的存储空间,可以随便你任意存放相片、视频、文档、ROM安装包等。擦除这个分区是完全安全的,只要你把分区中你需要的数据都备份到了你的电脑中。虽然一些用户安装的程序会使用这个分区保存它的数据和设置信息,擦除了这个分区,这些程序的数据,比如有些游戏的存档,就会全部丢失。在既有内部SD卡和外部SD卡的设备中,比如三星Galaxy S和一些平板电脑,/sdcard分区通常指向内部SD卡。外部SD卡,如果存在的话,会对应一个新的分区,每个设备都不一样。在三星Galaxy S手机中, /sdcard/sd代表的是外部SD卡,而其它设备,有可能是/sdcard2。与/sdcard不同,没有系统或应用程序数据会自动存放在外部SD卡中。外部SD卡中的所有数据都是用户自己添加进去的。在你把分区中需要的数据都备份到了你的电脑中之后,你可以安全的擦除这个分区。

    This is not a partition on the internal memory of the device but rather the SD card. In terms of usage, this is your storage space to use as you see fit, to store your media, documents, ROMs etc. on it. Wiping it is perfectly safe as long as you backup all the data you require from it, to your computer first. Though several user-installed apps save their data and settings on the SD card and wiping this partition will make you lose all that data.On devices with both an internal and an external SD card – devices like the Samsung Galaxy S and several tablets – the /sdcard partition is always used to refer to the internal SD card. For the external SD card – if present – an alternative partition is used, which differs from device to device. In case of Samsung Galaxy S series devices, it is /sdcard/sd while in many other devices, it is /sdcard2. Unlike /sdcard, no system or app data whatsoever is stored automatically on this external SD card and everything present on it has been added there by the user. You can safely wipe it after backing up any data from it that you need to save.

    /sd-ext

    这不是安卓系统的标准分区,但在第三方ROM届却很流行。它根本上是你SD卡上一个额外的分区,从外部功能表现上,与 /data分区的功能相同。一些第三方ROM,有一些特殊的功能叫做APP2SD+或者data2ext。这个功能在设备的内部存储空间比较小(也就是分配给/data分区的空间比较小)时非常有用。因此,需要安装更多程序,但内部空间又不够的用户,可以使用支持这个功能的第三方ROM,来获取额外的空间安装更多的应用程序。 擦除这个分区和擦除 /data分区的结果相同,你将会丢失联系人,短信、安装应用程序和设置。

    This is not a standard Android partition, but has become popular in the custom ROM scene. It is basically an additional partition on your SD card that acts as the /data partition when used with certain ROMs that have special features called APP2SD+ or data2ext enabled. It is especially useful on devices with little internal memory allotted to the /data partition. Thus, users who want to install more programs than the internal memory allows can make this partition and use it with a custom ROM that supports this feature, to get additional storage for installing their apps. Wiping this partition is essentially the same as wiping the /data partition – you lose your contacts, SMS, market apps and settings.

    到此,就结束了安卓各个分区的介绍。现在如果安装一个ROM时,安装前要求你擦除某个分区,你应该更加了解你要进行的操作的作用和结果,也知道你会丢失那些内容,而那些内容又不会丢失。你也知道应该备份那些内容,而那些又不需要备份。

    With this, we conclude our tour of Android partitions. Now whenever you install a ROM or mod that requires you to wipe certain partitions before the installation, you should be in a better position to know what you’re losing and what not and thus, you’ll know what to backup and what not.


    展开全文
  • 浅谈进程地址空间与虚拟存储空间

    万次阅读 多人点赞 2015-04-17 19:35:47
    早期的内存分配机制 在早期的计算机中,要运行一个程序,会把这些程序全都装入内存,程序都是直接运行在内存上的,也就是说程序中访问的内存...下面通过实例来说明当时的内存分配方法: 某台计算机总的内存大小...

    早期的内存分配机制

    在早期的计算机中,要运行一个程序,会把这些程序全都装入内存,程序都是直接运行在内存上的,也就是说程序中访问的内存地址都是实际的物理内存地址。当计算机同时运行多个程序时,必须保证这些程序用到的内存总量要小于计算机实际物理内存的大小。

     

    那当程序同时运行多个程序时,操作系统是如何为这些程序分配内存 的呢?下面通过实例来说明当时的内存分配方法:

     

    某台计算机总的内存大小是 128M ,现在同时运行两个程序 A 和 B , A 需占用内存 10M , B 需占用内存 110 。计算机在给程序分配内存时会采取这样的方法:先将内存中的前 10M 分配给程序 A ,接着再从内存中剩余的 118M 中划分出 110M 分配给程序 B 。这种分配方法可以保证程序 A 和程序 B 都能运行,但是这种简单的内存分配策略问题很多。

     

     

     

    早期的内存分配方法

     

    问题 1 :进程地址空间不隔离。由于程序都是直接访问物理内存,所以恶意程序可以随意修改别的进程的内存数据,以达到破坏的目的。有些非恶意的,但是有 bug 的程序也可能不小心修改了其它程序的内存数据,就会导致其它程序的运行出现异常。这种情况对用户来说是无法容忍的,因为用户希望使用计算机的时候,其中一个任务失败了,至少不能影响其它的任务。

     

    问题 2 :内存使用效率低。在 A 和 B 都运行的情况下,如果用户又运行了程序 C,而程序 C 需要 20M 大小的内存才能运行,而此时系统只剩下 8M 的空间可供使用,所以此时系统必须在已运行的程序中选择一个将该程序的数据暂时拷贝到硬盘上,释放出部分空间来供程序 C 使用,然后再将程序 C 的数据全部装入内存中运行。可以想象得到,在这个过程中,有大量的数据在装入装出,导致效率十分低下。

     

    问题 3 :程序运行的地址不确定。当内存中的剩余空间可以满足程序 C 的要求后,操作系统会在剩余空间中随机分配一段连续的 20M 大小的空间给程序 C 使用,因为是随机分配的,所以程序运行的地址是不确定的。

     

    分段

    为 了解决上述问题,人们想到了一种变通的方法,就是增加一个中间层,利用一种间接的地址访问方法访问物理内存。按照这种方法,程序中访问的内存地址不再是实际的物理内存地址,而是一个虚拟地址,然后由操作系统将这个虚拟地址映射到适当的物理内存地址上。这样,只要操作系统处理好虚拟地址到物理内存地址的映射,就可以保证不同的程序最终访问的内存地址位于不同的区域,彼此没有重叠,就可以达到内存地址空间隔离的效果。

     

    当创建一个进程时,操作系统会为该进程分配一个 4GB 大小的虚拟进程地址空间。之所以是 4GB ,是因为在 32 位的操作系统中,一个指针长度是 4 字节,而 4 字节指针的寻址能力是从 0x00000000~0xFFFFFFFF,最大值 0xFFFFFFFF 表示的即为 4GB 大小的容量。与虚拟地址空间相对的,还有一个物理地址空间,这个地址空间对应的是真实的物理内存。如果你的计算机上安装了 512M 大小的内存,那么这个物理地址空间表示的范围是 0x00000000~0x1FFFFFFF 。当操作系统做虚拟地址到物理地址映射时,只能映射到这一范围,操作系统也只会映射到这一范围。当进程创建时,每个进程都会有一个自己的 4GB 虚拟地址空间。要注意的是这个 4GB 的地址空间是“虚拟”的,并不是真实存在的,而且每个进程只能访问自己虚拟地址空间中的数据,无法访问别的进程中的数据,通过这种方法实现了进程间的地址隔离。那是不是这 4GB 的虚拟地址空间应用程序可以随意使用呢?很遗憾,在 Windows 系统下,这个虚拟地址空间被分成了 4 部分: NULL 指针区、用户区、 64KB 禁入区、内核区。

     

    1)NULL指针区 (0x00000000~0x0000FFFF): 如果进程中的一个线程试图操作这个分区中的数据,CPU就会引发非法访问。他的作用是,调用 malloc 等内存分配函数时,如果无法找到足够的内存空间,它将返回 NULL。而不进行安全性检查。它只是假设地址分配成功,并开始访问内存地址 0x00000000(NULL)。由于禁止访问内存的这个分区,因此会发生非法访问现象,并终止这个进程的运行。


    2)用户模式分区 ( 0x00010000~0xBFFEFFFF):这个分区中存放进程的私有地址空间。一个进程无法以任何方式访问另外一个进程驻留在这个分区中的数据 (相同 exe,通过 copy-on-write 来完成地址隔离)。(在windows中,所有 .exe 和动态链接库都载入到这一区域。系统同时会把该进程可以访问的所有内存映射文件映射到这一分区)。


    2)隔离区 (0xBFFF0000~0xBFFFFFFF):这个分区禁止进入。任何试图访问这个内存分区的操作都是违规的。微软保留这块分区的目的是为了简化操作系统的现实。


    3)内核区 (0xC0000000~0xFFFFFFFF):这个分区存放操作系统驻留的代码。线程调度、内存管理、文件系统支持、网络支持和所有设备驱动程序代码都在这个分区加载。这个分区被所有进程共享。

     

    应用程序能使用的只是用户区而已,大约 2GB 左右 ( 最大可以调整到 3GB) 。内核区为 2GB ,内核区保存的是系统线程调度、内存管理、设备驱动等数据,这部分数据供所有的进程共享,但应用程序是不能直接访问的。

     

    人们之所以要创建一个虚拟地址空间,目的是为了解决进程地址空间隔离的问题。但程序要想执行,必须运行在真实的内存上,所以,必须在虚拟地址与物理地址间建立一种映射关系。这样,通过映射机制,当程序访问虚拟地址空间上的某个地址值时,就相当于访问了物理地址空间中的另一个值。人们想到了一种分段(Sagmentation) 的方法,它的思想是在虚拟地址空间和物理地址空间之间做一一映射。比如说虚拟地址空间中某个 10M 大小的空间映射到物理地址空间中某个 10M 大小的空间。这种思想理解起来并不难,操作系统保证不同进程的地址空间被映射到物理地址空间中不同的区域上,这样每个进程最终访问到的。

     

    物理地址空间都是彼此分开的。通过这种方式,就实现了进程间的地址隔离。还是以实例说明,假设有两个进程 A 和 B ,进程 A 所需内存大小为 10M ,其虚拟地址空间分布在 0x00000000 到 0x00A00000 ,进程 B 所需内存为 100M ,其虚拟地址空间分布为 0x00000000 到 0x06400000 。那么按照分段的映射方法,进程 A 在物理内存上映射区域为 0x00100000 到 0x00B00000 ,,进程 B 在物理内存上映射区域为0x00C00000 到 0x07000000 。于是进程 A 和进程 B 分别被映射到了不同的内存区间,彼此互不重叠,实现了地址隔离。从应用程序的角度看来,进程 A 的地址空间就是分布在 0x00000000 到 0x00A00000 ,在做开发时,开发人员只需访问这段区间上的地址即可。应用程序并不关心进程 A 究竟被映射到物理内存的那块区域上了,所以程序的运行地址也就是相当于说是确定的了。 下图显示的是分段方式的内存映射方法: 

    分段方式的内存映射方法

     

    这种分段的映射方法虽然解决了上述中的问题一和问题三,但并没能解决问题二,即内存的使用效率问题。在分段的映射方法中,每次换入换出内存的都是整个程序, 这样会造成大量的磁盘访问操作,导致效率低下。所以这种映射方法还是稍显粗糙,粒度比较大。实际上,程序的运行有局部性特点,在某个时间段内,程序只是访问程序的一小部分数据,也就是说,程序的大部分数据在一个时间段内都不会被用到。基于这种情况,人们想到了粒度更小的内存分割和映射方法,这种方法就是分页 (Paging) 。  

     

    分页

    分页的基本方法是,将地址空间分成许多的页。每页的大小由 CPU 决定,然后由操作系统选择页的大小。目前 Inter 系列的 CPU 支持 4KB 或 4MB 的页大小,而 PC上目前都选择使用 4KB 。按这种选择, 4GB 虚拟地址空间共可以分成 1048576 页, 512M 的物理内存可以分为 131072 个页。显然虚拟空间的页数要比物理空间的页数多得多

     

    在分段的方法中,每次程序运行时总是把程序全部装入内存,而分页的方法则有所不同。分页的思想是程序运行时用到哪页就为哪页分配内存,没用到的页暂时保留在硬盘上。当用到这些页时再在物理地址空间中为这些页分配内存,然后建立虚拟地址空间中的页和刚分配的物理内存页间的映射。

     

    下面通过介绍一个可执行文件的装载过程来说明分页机制的实现方法。一个可执行文件 (PE 文件 ) 其实就是一些编译链接好的数据和指令的集合,它也会被分成很多页,在 PE 文件执行的过程中,它往内存中装载的单位就是页。当一个 PE 文件被执行时,操作系统会先为该程序创建一个 4GB 的进程虚拟地址空间。前面介绍过,虚拟地址空间只是一个中间层而已,它的功能是利用一种映射机制将虚拟地址空间映射到物理地址空间,所以,创建 4GB 虚拟地址空间其实并不是要真的创建空间,只是要创建那种映射机制所需要的数据结构而已,这种数据结构就是页目和页表。

     

    当创建完虚拟地址空间所需要的数据结构后,进程开始读取 PE 文件的第一页。在PE 文件的第一页包含了 PE 文件头和段表等信息,进程根据文件头和段表等信息,将 PE 文件中所有的段一一映射到虚拟地址空间中相应的页 (PE 文件中的段的长度都是页长的整数倍 ) 。这时 PE 文件的真正指令和数据还没有被装入内存中,操作系统只是据 PE 文件的头部等信息建立了 PE 文件和进程虚拟地址空间中页的映射关系而已。当 CPU 要访问程序中用到的某个虚拟地址时,当 CPU 发现该地址并没有相相关联的物理地址时, CPU 认为该虚拟地址所在的页面是个空页面, CPU 会认为这是个页错误 (Page Fault) , CPU 也就知道了操作系统还未给该 PE 页面分配内存,CPU 会将控制权交还给操作系统。操作系统于是为该 PE 页面在物理空间中分配一个页面,然后再将这个物理页面与虚拟空间中的虚拟页面映射起来,然后将控制权再还给进程,进程从刚才发生页错误的位置重新开始执行。由于此时已为 PE 文件的那个页面分配了内存,所以就不会发生页错误了。随着程序的执行,页错误会不断地产生,操作系统也会为进程分配相应的物理页面来满足进程执行的需求。

     

    分页方法的核心思想就是当可执行文件执行到第 x 页时,就为第 x 页分配一个内存页 y ,然后再将这个内存页添加到进程虚拟地址空间的映射表中 , 这个映射表就相当于一个 y=f(x) 函数。应用程序通过这个映射表就可以访问到 x 页关联的 y 页了。

     

    逻辑地址、线性地址、物理地址和虚拟地址的区别

    逻辑地址(Logical Address) 是指由程式产生的和段相关的偏移地址部分。例如,你在进行 C 语言指针编程中,能读取指针变量本身值( &操作 ),实际上这个值就是逻辑地址,他是相对于你当前进程数据段的地址,不和绝对物理地址相干。只有在 Intel 实模式下,逻辑地址才和物理地址相等(因为实模式没有分段或分页机制,cpu不进行自动地址转换);逻辑也就是在Intel保护模式下程式执行代码段限长内的偏移地址(假定代码段、数据段如果完全相同)。应用程式员仅需和逻辑地址打交道,而分段和分页机制对你来说是完全透明的,仅由系统编程人员涉及。应用程式员虽然自己能直接操作内存,那也只能在操作系统给你分配的内存段操作。


    线性地址(Linear Address) 是逻辑地址到物理地址变换之间的中间层。程式代码会产生逻辑地址,或说是段中的偏移地址,加上相应段的基地址就生成了一个线性地址。如果启用了分页机制,那么线性地址能再经变换以产生一个物理地址。若没有启用分页机制,那么线性地址直接就是物理地址。Intel 80386 的线性地址空间容量为 4G(2的32次方即32根地址总线寻址)。


    物理地址(Physical Address) 是指出目前 CPU 外部地址总线上的寻址物理内存的地址信号,是地址变换的最终结果地址。如果启用了分页机制,那么线性地址会使用页目录和页表中的项变换成物理地址。如果没有启用分页机制,那么线性地址就直接成为物理地址了。


    虚拟内存(Virtual Memory)是指计算机呈现出要比实际拥有的内存大得多的内存量。因此他允许程式员编制并运行比实际系统拥有的内存大得多的程式。这使得许多大型项目也能够在具有有限内存资源的系统上实现。一个非常恰当的比喻是:你不必非常长的轨道就能让一列火车从上海开到北京。你只需要足够长的铁轨(比如说3公里)就能完成这个任务。采取的方法是把后面的铁轨即时铺到火车的前面,只要你的操作足够快并能满足需求,列车就能象在一条完整的轨道上运行。这也就是虚拟内存管理需要完成的任务。在 Linux0.11 内核中,给每个程式(进程)都划分了总容量为 64MB 的虚拟内存空间。因此程式的逻辑地址范围是 0x0000000 到 0x4000000。有时我们也把逻辑地址称为 虚拟地址。因为和虚拟内存空间的概念类似,逻辑地址也是和实际物理内存容量无关的。逻辑地址和物理地址的“差距”是 0xC0000000,是由于虚拟地址->线性地址->物理地址映射正好差这个值。这个值是由操作系统指定的。机理逻辑地址(或称为虚拟地址)到线性地址是由CPU的段机制自动转换的。如果没有开启分页管理,则线性地址就是物理地址。如果开启了分页管理,那么系统程式需要参和线性地址到物理地址的转换过程。具体是通过设置页目录表和页表项进行的。

     

    转自:游手好弦 信步涂鸦

    展开全文
  • 决策树:特征分布空间划分方法

    千次阅读 2014-03-25 14:10:23
    如何快速而准确地找到查询点的近邻,不少人提出了很多高维空间索引结构和近似查询的算法。 一般说来,索引结构中相似性查询有两种基本的方式: 一种是范围查询,范围查询时给定查询点和查询距离阈值,从数据集中查找...

    前言:懒惰的原因是因为时间太少,不能够去仔细的探索学习,拿来主义丧失了很多快乐!

    K近邻算法的实现:KD树

    原文链接:http://blog.csdn.net/v_july_v/article/details/8203674/

    2.0、背景

         之前blog内曾经介绍过SIFT特征匹配算法,特征点匹配和数据库查、图像检索本质上是同一个问题,都可以归结为一个通过距离函数在高维矢量之间进行相似性检索的问题,如何快速而准确地找到查询点的近邻,不少人提出了很多高维空间索引结构和近似查询的算法。

        一般说来,索引结构中相似性查询有两种基本的方式:

    1. 一种是范围查询,范围查询时给定查询点和查询距离阈值,从数据集中查找所有与查询点距离小于阈值的数据
    2. 另一种是K近邻查询,就是给定查询点及正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,它就是最近邻查询。

        同样,针对特征点匹配也有两种方法:

    • 最容易的办法就是线性扫描,也就是我们常说的穷举搜索,依次计算样本集E中每个样本到输入实例点的距离,然后抽取出计算出来的最小距离的点即为最近邻点。此种办法简单直白,但当样本集或训练集很大时,它的缺点就立马暴露出来了,举个例子,在物体识别的问题中,可能有数千个甚至数万个SIFT特征点,而去一一计算这成千上万的特征点与输入实例点的距离,明显是不足取的。
    • 另外一种,就是构建数据索引,因为实际数据一般都会呈现簇状的聚类形态,因此我们想到建立数据索引,然后再进行快速匹配。索引树是一种树结构索引方法,其基本思想是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠,其代表就是k-d树;后者划分空间相互有交叠,其代表为R树。

        而关于R树本blog内之前已有介绍(同时,关于基于R树的最近邻查找,还可以看下这篇文章:http://blog.sina.com.cn/s/blog_72e1c7550101dsc3.html),本文着重介绍k-d树。

        1975年,来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文:Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和阐述的了如下图形式的把空间划分为多个部分的k-d树。

    2.1、什么是KD树

        Kd-树是K-dimension tree的缩写,是对数据点在k维空间(如二维(x,y),三维(x,y,z),k维(x1,y,z..)中划分的一种数据结构,主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。本质上说,Kd-树就是一种平衡二叉树。

        首先必须搞清楚的是,k-d树是一种空间划分树,说白了,就是把整个空间划分为特定的几个部分,然后在特定空间的部分内进行相关搜索操作。想像一个三维(多维有点为难你的想象力了)空间,kd树按照一定的划分规则把这个三维空间划分了多个空间,如下图所示:

    2.2、KD树的构建

        kd树构建的伪代码如下图所示:

        再举一个简单直观的实例来介绍k-d树构建算法。假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间内,如下图所示。为了能有效的找到最近邻,k-d树采用分而治之的思想,即将整个空间划分为几个小部分,首先,粗黑线将空间一分为二,然后在两个子空间中,细黑直线又将整个空间划分为四部分,最后虚黑直线将这四部分进一步划分。

        6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}构建kd树的具体步骤为:

    1. 确定:split域=x。具体是:6个数据点在x,y维度上的数据方差分别为39,28.63,所以在x轴上方差更大,故split域值为x;
    2. 确定:Node-data = (7,2)。具体是:根据x维上的值将数据排序,6个数据的中值(所谓中值,即中间大小的值)为7,所以Node-data域位数据点(7,2)。这样,该节点的分割超平面就是通过(7,2)并垂直于:split=x轴的直线x=7;
    3. 确定:左子空间和右子空间。具体是:分割超平面x=7将整个空间分为两部分:x<=7的部分为左子空间,包含3个节点={(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点={(9,6),(8,1)};
        如上算法所述,kd树的构建是一个递归过程,我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点(5,4)和(9,6),同时将空间和数据集进一步细分,如此往复直到空间中只包含一个数据点。

        与此同时,经过对上面所示的空间划分之后,我们可以看出,点(7,2)可以为根结点,从根结点出发的两条红粗斜线指向的(5,4)和(9,6)则为根结点的左右子结点,而(2,3),(4,7)则为(5,4)的左右孩子(通过两条细红斜线相连),最后,(8,1)为(9,6)的左孩子(通过细红斜线相连)。如此,便形成了下面这样一棵k-d树:

     

        k-d树的数据结构

        针对上表给出的kd树的数据结构,转化成具体代码如下所示(注,本文以下代码分析基于Rob Hess维护的sift库)

    /** a node in a k-d tree */
    struct kd_node
    {
    	int ki;                      /**< partition key index *///关键点直方图方差最大向量系列位置
    	double kv;                   /**< partition key value *///直方图方差最大向量系列中最中间模值
    	int leaf;                    /**< 1 if node is a leaf, 0 otherwise */
    	struct feature* features;    /**< features at this node */
    	int n;                       /**< number of features */
    	struct kd_node* kd_left;     /**< left child */
    	struct kd_node* kd_right;    /**< right child */
    };

        也就是说,如之前所述,kd树中,kd代表k-dimension,每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面,用垂直于坐标轴的超平面将空间分为两个部分,这样递归的从根节点不停的划分,直到没有实例为止。经典的构造k-d tree的规则如下:

    1. 随着树的深度增加,循环的选取坐标轴,作为分割超平面的法向量。对于3-d tree来说,根节点选取x轴,根节点的孩子选取y轴,根节点的孙子选取z轴,根节点的曾孙子选取x轴,这样循环下去。
    2. 每次均为所有对应实例的中位数的实例作为切分点,切分点作为父节点,左右两侧为划分的作为左右两子树。

        对于n个实例的k维数据来说,建立kd-tree的时间复杂度为O(k*n*logn)。

        以下是构建k-d树的代码:

    struct kd_node* kdtree_build( struct feature* features, int n )
    {
    	struct kd_node* kd_root;
    
    	if( ! features  ||  n <= 0 )
    	{
    		fprintf( stderr, "Warning: kdtree_build(): no features, %s, line %d\n",
    				__FILE__, __LINE__ );
    		return NULL;
    	}
    
    	//初始化
    	kd_root = kd_node_init( features, n );  //n--number of features,initinalize root of tree.
    	expand_kd_node_subtree( kd_root );  //kd tree expand
    
    	return kd_root;
    }

        上面的涉及初始化操作的两个函数kd_node_init,及expand_kd_node_subtree代码分别如下所示:

    static struct kd_node* kd_node_init( struct feature* features, int n )
    {                                     //n--number of features
    	struct kd_node* kd_node;
    
    	kd_node = (struct kd_node*)(malloc( sizeof( struct kd_node ) ));
    	memset( kd_node, 0, sizeof( struct kd_node ) ); //0填充
    	kd_node->ki = -1; //???????
    	kd_node->features = features;
    	kd_node->n = n;
    
    	return kd_node;
    }
    static void expand_kd_node_subtree( struct kd_node* kd_node )
    {
    	/* base case: leaf node */
    	if( kd_node->n == 1  ||  kd_node->n == 0 )
    	{   //叶节点               //伪叶节点
    		kd_node->leaf = 1;
    		return;
    	}
    
    	assign_part_key( kd_node ); //get ki,kv
    	partition_features( kd_node ); //creat left and right children,特征点ki位置左树比右树模值小,kv作为分界模值
                                     //kd_node中关键点已经排序
    	if( kd_node->kd_left )
    		expand_kd_node_subtree( kd_node->kd_left );
    	if( kd_node->kd_right )
    		expand_kd_node_subtree( kd_node->kd_right );
    }

        构建完kd树之后,如今进行最近邻搜索呢?从下面的动态gif图中,你是否能看出些许端倪呢?


        k-d树算法可以分为两大部分,除了上部分有关k-d树本身这种数据结构建立的算法,另一部分是在建立的k-d树上各种诸如插入,删除,查找(最邻近查找)等操作涉及的算法。下面,咱们依次来看kd树的插入、删除、查找操作。

    2.3、KD树的插入

        元素插入到一个K-D树的方法和二叉检索树类似。本质上,在偶数层比较x坐标值,而在奇数层比较y坐标值。当我们到达了树的底部,(也就是当一个空指针出现),我们也就找到了结点将要插入的位置。生成的K-D树的形状依赖于结点插入时的顺序。给定N个点,其中一个结点插入和检索的平均代价是O(log2N)。

        下面4副图(来源:中国地质大学电子课件)说明了插入顺序为(a) Chicago, (b) Mobile, (c) Toronto, and (d) Buffalo,建立空间K-D树的示例:


        应该清楚,这里描述的插入过程中,每个结点将其所在的平面分割成两部分。因比,Chicago 将平面上所有结点分成两部分,一部分所有的结点x坐标值小于35,另一部分结点的x坐标值大于或等于35。同样Mobile将所有x坐标值大于35的结点以分成两部分,一部分结点的Y坐标值是小于10,另一部分结点的Y坐标值大于或等于10。后面的Toronto、Buffalo也按照一分为二的规则继续划分。

    2.4、KD树的删除

        KD树的删除可以用递归程序来实现。我们假设希望从K-D树中删除结点(a,b)。如果(a,b)的两个子树都为空,则用空树来代替(a,b)。否则,在(a,b)的子树中寻找一个合适的结点来代替它,譬如(c,d),则递归地从K-D树中删除(c,d)。一旦(c,d)已经被删除,则用(c,d)代替(a,b)。假设(a,b)是一个X识别器,那么, 它得替代节点要么是(a,b)左子树中的X坐标最大值的结点,要么是(a,b)右子树中x坐标最小值的结点
        也就是说,跟普通二叉树( 包括如下图所示的红黑树)结点的删除是同样的思想:用被删除节点A的左子树的最右节点或者A的右子树的最左节点作为替代A的节点( 比如,下图红黑树中,若要删除根结点26,第一步便是用23或28取代根结点26)。
       当(a,b)的右子树为空时,找到(a,b)左子树中具有x坐标最大的结点,譬如(c,d),将(a,b)的左子树放到(c,d)的右子树中,且在树中从它的上一层递归地应用删除过程(也就是(a,b)的左子树) 。
        下面来举一个实际的例子( 来源:中国地质大学电子课件,原课件错误已经在下文中订正),如下图所示,原始图像及对应的kd树,现在要删除图中的A结点,请看一系列删除步骤:
        要删除上图中结点A,选择结点A的右子树中X坐标值最小的结点,这里是C,C成为根,如下图:
         从C的右子树中找出一个结点代替先前C的位置,
        这里是D,并将D的左子树转为它的右子树,D代替先前C的位置,如下图:
        在D的新右子树中,找X坐标最小的结点,这里为H,H代替D的位置,
        在D的右子树中找到一个Y坐标最小的值,这里是I,将I代替原先H的位置,从而A结点从图中顺利删除,如下图所示:
        从一个K-D树中删除结点(a,b)的问题变成了在(a,b)的子树中寻找x坐标为最小的结点。不幸的是寻找最小x坐标值的结点比二叉检索树中解决类似的问题要复杂得多。特别是虽然最小x坐标值的结点一定在x识别器的左子树中,但它同样可在y识别器的两个子树中。因此关系到检索,且必须注意检索坐标,以使在每个奇数层仅检索2个子树中的一个。
        从K-D树中删除一个结点是代价很高的,很清楚删除子树的根受到子树中结点个数的限制。用TPL(T)表示树T总的路径长度。可看出树中子树大小的总和为TPL(T)+N。 以随机方式插入N个点形成树的TPL是O(N*log2N),这就意味着从一个随机形成的K-D树中删除一个随机选取的结点平均代价的上界是O(log2N) 。

    2.5、KD树的最近邻搜索算法

        现实生活中有许多问题需要在多维数据的快速分析和快速搜索,对于这个问题最常用的方法是所谓的kd树。在k-d树中进行数据的查找也是特征匹配的重要环节,其目的是检索在k-d树中与查询点距离最近的数据点。在一个N维的笛卡儿空间在两个点之间的距离是由下述公式确定:

    2.5.1、k-d树查询算法的伪代码

        k-d树查询算法的伪代码如下所示:

    算法:k-d树最邻近查找
    输入:Kd,    //k-d tree类型
         target  //查询数据点
    输出:nearest, //最邻近数据点
         dist      //最邻近数据点和查询点间的距离
    
    1. If Kd为NULL,则设dist为infinite并返回
    2. //进行二叉查找,生成搜索路径
       Kd_point = &Kd;                   //Kd-point中保存k-d tree根节点地址
       nearest = Kd_point -> Node-data;  //初始化最近邻点
    
       while(Kd_point)
         push(Kd_point)到search_path中; //search_path是一个堆栈结构,存储着搜索路径节点指针
    
          If Dist(nearest,target) > Dist(Kd_point -> Node-data,target)
           nearest  = Kd_point -> Node-data;    //更新最近邻点
           Min_dist = Dist(Kd_point,target);  //更新最近邻点与查询点间的距离  ***/
         s = Kd_point -> split;                       //确定待分割的方向
    
         If target[s] <= Kd_point -> Node-data[s]     //进行二叉查找
           Kd_point = Kd_point -> left;
         else
           Kd_point = Kd_point ->right;
       End while
    
    3. //回溯查找
       while(search_path != NULL)
         back_point = 从search_path取出一个节点指针;   //从search_path堆栈弹栈
         s = back_point -> split;                      //确定分割方向
    
         If Dist(target[s],back_point -> Node-data[s]) < Max_dist   //判断还需进入的子空间
           If target[s] <= back_point -> Node-data[s]
             Kd_point = back_point -> right;  //如果target位于左子空间,就应进入右子空间
           else
             Kd_point = back_point -> left;    //如果target位于右子空间,就应进入左子空间
           将Kd_point压入search_path堆栈;
    
         If Dist(nearest,target) > Dist(Kd_Point -> Node-data,target)
           nearest  = Kd_point -> Node-data;                 //更新最近邻点
           Min_dist = Dist(Kd_point -> Node-data,target);  //更新最近邻点与查询点间的距离的
       End while 

       读者来信点评@yhxyhxyhx,在“将Kd_point压入search_path堆栈;”这行代码后,应该是调到步骤2再往下走二分搜索的逻辑一直到叶结点,我写了一个递归版本的二维kd tree的搜索函数你对比的看看:

    void innerGetClosest(NODE* pNode, PT point, PT& res, int& nMinDis)
    {
    	if (NULL == pNode)
    		return;
    	int nCurDis = abs(point.x - pNode->pt.x) + abs(point.y - pNode->pt.y);
    	if (nMinDis < 0 || nCurDis < nMinDis)
    	{
    		nMinDis = nCurDis;
    		res = pNode->pt;
    	}
    	if (pNode->splitX && point.x <= pNode->pt.x || !pNode->splitX && point.y <= pNode->pt.y)
    		innerGetClosest(pNode->pLft, point, res, nMinDis);
    	else
    		innerGetClosest(pNode->pRgt, point, res, nMinDis);
    	int rang = pNode->splitX ? abs(point.x - pNode->pt.x) : abs(point.y - pNode->pt.y);
    	if (rang > nMinDis)
    		return;
    	NODE* pGoInto = pNode->pLft;
    	if (pNode->splitX && point.x > pNode->pt.x || !pNode->splitX && point.y > pNode->pt.y)
    		pGoInto = pNode->pRgt;
    	innerGetClosest(pGoInto, point, res, nMinDis);
    }

        下面,以两个简单的实例(例子来自图像局部不变特性特征与描述一书)来描述最邻近查找的基本思路。

    2.5.2、举例:查询点(2.1,3.1)

        星号表示要查询的点(2.1,3.1)。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点(2,3)。而找到的叶子节点并不一定就是最邻近的,最邻近肯定距离查询点更近,应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻,还需要进行相关的‘回溯'操作。也就是说,算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。

        以查询(2.1,3.1)为例:

    1. 二叉树搜索:先从(7,2)点开始进行二叉查找,然后到达(5,4),最后到达(2,3),此时搜索路径中的节点为<(7,2),(5,4),(2,3)>,首先以(2,3)作为当前最近邻点,计算其到查询点(2.1,3.1)的距离为0.1414,
    2. 回溯查找:在得到(2,3)为查询点的最近点之后,回溯到其父节点(5,4),并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以(2.1,3.1)为圆心,以0.1414为半径画圆,如下图所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)节点右子空间中(图中灰色区域)去搜索;
    3. 最后,再回溯到(7,2),以(2.1,3.1)为圆心,以0.1414为半径的圆更不会与x = 7超平面交割,因此不用进入(7,2)右子空间进行查找。至此,搜索路径中的节点已经全部回溯完,结束整个搜索,返回最近邻点(2,3),最近距离为0.1414。


    2.5.3、举例:查询点2,4.5

        一个复杂点了例子如查找点为(2,4.5),具体步骤依次如下:

    1. 同样先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,但(4,7)与目标查找点的距离为3.202,而(5,4)与查找点之间的距离为3.041,所以(5,4)为查询点的最近点;
    2. 以(2,4.5)为圆心,以3.041为半径作圆,如下图所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找,也就是将(2,3)节点加入搜索路径中得<(7,2),(2,3)>;于是接着搜索至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5;
    3. 回溯查找至(5,4),直到最后回溯到根结点(7,2)的时候,以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如下图所示。至此,搜索路径回溯完,返回最近邻点(2,3),最近距离1.5。

        上述两次实例表明,当查询点的邻域与分割超平面两侧空间交割时,需要查找另一侧子空间,导致检索过程复杂,效率下降。

        一般来讲,最临近搜索只需要检测几个叶子结点即可,如下图所示:   

        但是,如果当实例点的分布比较糟糕时,几乎要遍历所有的结点,如下所示:

        研究表明N个节点的K维k-d树搜索过程时间复杂度为:tworst=O(kN1-1/k)。

        同时,以上为了介绍方便,讨论的是二维或三维情形。但在实际的应用中,如SIFT特征矢量128维,SURF特征矢量64维,维度都比较大,直接利用k-d树快速检索(维数不超过20)的性能急剧下降,几乎接近贪婪线性扫描。假设数据集的维数为D,一般来说要求数据的规模N满足N»2D,才能达到高效的搜索。所以这就引出了一系列对k-d树算法的改进:BBF算法,和一系列M树、VP树、MVP树等高维空间索引树(下文2.6节kd树近邻搜索算法的改进:BBF算法,与2.7节球树、M树、VP树、MVP树)。

    2.6、kd树近邻搜索算法的改进:BBF算法

        咱们顺着上一节的思路,参考统计学习方法一书上的内容,再来总结下kd树的最近邻搜索算法:

    输入:以构造的kd树,目标点x;
    输出:x 的最近邻
    算法步骤如下:
    1. 在kd树种找出包含目标点x的叶结点:从根结点出发,递归地向下搜索kd树。若目标点x当前维的坐标小于切分点的坐标,则移动到左子结点,否则移动到右子结点,直到子结点为叶结点为止。
    2. 以此叶结点为“当前最近点”。
    3. 递归的向上回溯,在每个结点进行以下操作:
      (a)如果该结点保存的实例点比当前最近点距离目标点更近,则更新“当前最近点”,也就是说以该实例点为“当前最近点”。
      (b)当前最近点一定存在于该结点一个子结点对应的区域,检查子结点的父结点的另一子结点对应的区域是否有更近的点。具体做法是,检查另一子结点对应的区域是否以目标点位球心,以目标点与“当前最近点”间的距离为半径的圆或超球体相交:
      如果相交,可能在另一个子结点对应的区域内存在距目标点更近的点,移动到另一个子结点,接着,继续递归地进行最近邻搜索;
      如果不相交,向上回溯。
    4. 回退到根结点时,搜索结束,最后的“当前最近点”即为x 的最近邻点。

        如果实例点是随机分布的,那么kd树搜索的平均计算复杂度是O(NlogN),这里的N是训练实例树。所以说,kd树更适用于训练实例数远大于空间维数时的k近邻搜索,当空间维数接近训练实例数时,它的效率会迅速下降,一降降到“解放前”:线性扫描的速度。

        也正因为上述k最近邻搜索算法的第4个步骤中的所述:“回退到根结点时,搜索结束”,每个最近邻点的查询比较完成过程最终都要回退到根结点而结束,而导致了许多不必要回溯访问和比较到的结点,这些多余的损耗在高维度数据查找的时候,搜索效率将变得相当之地下,那有什么办法可以改进这个原始的kd树最近邻搜索算法呢?

        从上述标准的kd树查询过程可以看出其搜索过程中的“回溯”是由“查询路径”决定的,并没有考虑查询路径上一些数据点本身的一些性质。一个简单的改进思路就是将“查询路径”上的结点进行排序,如按各自分割超平面(也称bin)与查询点的距离排序,也就是说,回溯检查总是从优先级最高(Best Bin)的树结点开始。

        针对此BBF机制,读者Feng&书童点评道:

    1. 在某一层,分割面是第ki维,分割值是kv,那么 abs(q[ki]-kv) 就是没有选择的那个分支的优先级,也就是计算的是那一维上的距离;
    2. 同时,从优先队列里面取节点只在某次搜索到叶节点后才发生,计算过距离的节点不会出现在队列的,比如1~10这10个节点,你第一次搜索到叶节点的路径是1-5-7,那么1,5,7是不会出现在优先队列的。换句话说,优先队列里面存的都是查询路径上节点对应的相反子节点,比如:搜索左子树,就把对应这一层的右节点存进队列。

        如此,就引出了本节要讨论的kd树最近邻搜索算法的改进:BBF(Best-Bin-First)查询算法,它是由发明sift算法的David Lowe在1997的一篇文章中针对高维数据提出的一种近似算法,此算法能确保优先检索包含最近邻点可能性较高的空间,此外,BBF机制还设置了一个运行超时限定。采用了BBF查询机制后,kd树便可以有效的扩展到高维数据集上。

        伪代码如下图所示(图取自图像局部不变特性特征与描述一书):

        还是以上面的查询(2,4.5)为例,搜索的算法流程为:

    1. 将(7,2)压人优先队列中;
    2. 提取优先队列中的(7,2),由于(2,4.5)位于(7,2)分割超平面的左侧,所以检索其左子结点(5,4)。同时,根据BBF机制”搜索左/右子树,就把对应这一层的兄弟结点即右/左结点存进队列”,将其(5,4)对应的兄弟结点即右子结点(9,6)压人优先队列中,此时优先队列为{(9,6)},最佳点为(7,2);然后一直检索到叶子结点(4,7),此时优先队列为{(2,3),(9,6)},“最佳点”则为(5,4);
    3. 提取优先级最高的结点(2,3),重复步骤2,直到优先队列为空。
        如你在下图所见到的那样(话说,用鼠标在图片上写字着实不好写):

    2.7、球树、M树、VP树、MVP树

    2.7.1、球树

        咱们来针对上文内容总结回顾下,针对下面这样一棵kd树:

        现要找它的最近邻。

        通过上文2.5节,总结来说,我们已经知道:

    1、为了找到一个给定目标点的最近邻,需要从树的根结点开始向下沿树找出目标点所在的区域,如下图所示,给定目标点,用星号标示,我们似乎一眼看出,有一个点离目标点最近,因为它落在以目标点为圆心以较小长度为半径的虚线圆内,但为了确定是否可能还村庄一个最近的近邻,我们会先检查叶节点的同胞结点,然叶节点的同胞结点在图中所示的阴影部分,虚线圆并不与之相交,所以确定同胞叶结点不可能包含更近的近邻。

    2、于是我们回溯到父节点,并检查父节点的同胞结点,父节点的同胞结点覆盖了图中所有横线X轴上的区域。因为虚线圆与右上方的矩形(KD树把二维平面划分成一个一个矩形)相交...

        如上,我们看到,KD树是可用于有效寻找最近邻的一个树结构,但这个树结构其实并不完美,当处理不均匀分布的数据集时便会呈现出一个基本冲突:既邀请树有完美的平衡结构,又要求待查找的区域近似方形,但不管是近似方形,还是矩形,甚至正方形,都不是最好的使用形状,因为他们都有角。

            

        什么意思呢?就是说,在上图中,如果黑色的实例点离目标点星点再远一点,那么势必那个虚线圆会如红线所示那样扩大,以致与左上方矩形的右下角相交,既然相交了,那么势必又必须检查这个左上方矩形,而实际上,最近的点离星点的距离很近,检查左上方矩形区域已是多余。于此我们看见,KD树把二维平面划分成一个一个矩形,但矩形区域的角却是个难以处理的问题。

        解决的方案就是使用如下图所示的球树:

    先从球中选择一个离球的中心最远的点,然后选择第二个点离第一个点最远,将球中所有的点分配到离这两个聚类中心最近的一个上,然后计算每个聚类的中心,以及聚类能够包含它所有数据点所需的最小半径。这种方法的优点是分裂一个包含n个殊绝点的球的成本只是随n呈线性增加。

        使用球树找出给定目标点的最近邻方法是,首先自上而下贯穿整棵树找出包含目标点所在的叶子,并在这个球里找出与目标点最靠近的点,这将确定出目标点距离它的最近邻点的一个上限值,然后跟KD树查找一样,检查同胞结点,如果目标点到同胞结点中心的距离超过同胞结点的半径与当前的上限值之和,那么同胞结点里不可能存在一个更近的点;否则的话,必须进一步检查位于同胞结点以下的子树。

        如下图,目标点还是用一个星表示,黑色点是当前已知的的目标点的最近邻,灰色球里的所有内容将被排除,因为灰色球的中心点离的太远,所以它不可能包含一个更近的点,像这样,递归的向树的根结点进行回溯处理,检查所有可能包含一个更近于当前上限值的点的球。

        球树是自上而下的建立,和KD树一样,根本问题就是要找到一个好的方法将包含数据点集的球分裂成两个,在实践中,不必等到叶子结点只有两个胡数据点时才停止,可以采用和KD树一样的方法,一旦结点上的数据点打到预先设置的最小数量时,便可提前停止建树过程。

        也就是上面所述,先从球中选择一个离球的中心最远的点,然后选择第二个点离第一个点最远,将球中所有的点分配到离这两个聚类中心最近的一个上,然后计算每个聚类的中心,以及聚类能够包含它所有数据点所需的最小半径。这种方法的优点是分裂一个包含n个殊绝点的球的成本只是随n呈线性增加(注:本小节内容主要来自参考条目19:数据挖掘实用机器学习技术,[新西兰]Ian H.Witten 著,第4章4.7节)。

    2.7.2、VP树与MVP树简介

        高维特征向量的距离索引问题是基于内容的图像检索的一项关键技术,目前经常采用的解决办法是首先对高维特征空间做降维处理,然后采用包括四叉树、kd树、R树族等在内的主流多维索引结构,这种方法的出发点是:目前的主流多维索引结构在处理维数较低的情况时具有比较好的效率,但对于维数很高的情况则显得力不从心(即所谓的维数危机) 。

        实验结果表明当特征空间的维数超过20 的时候,效率明显降低,而可视化特征往往采用高维向量描述,一般情况下可以达到10^2的量级,甚至更高。在表示图像可视化特征的高维向量中各维信息的重要程度是不同的,通过降维技术去除属于次要信息的特征向量以及相关性较强的特征向量,从而降低特征空间的维数,这种方法已经得到了一些实际应用。

        然而这种方法存在不足之处采用降维技术可能会导致有效信息的损失,尤其不适合于处理特征空间中的特征向量相关性很小的情况。另外主流的多维索引结构大都针对欧氏空间,设计需要利用到欧氏空间的几何性质,而图像的相似性计算很可能不限于基于欧氏距离。这种情况下人们越来越关注基于距离的度量空间高维索引结构可以直接应用于高维向量相似性查询问题。

        度量空间中对象之间的距离度量只能利用三角不等式性质,而不能利用其他几何性质。向量空间可以看作由实数坐标串组成的特殊度量空间,目前针对度量空间的高维索引问题提出的索引结构有很多种大致可以作如下分类,如下图所示:

        
        其中,VP树和MVP树中特征向量的举例表示为:

         读者点评:

    1. UESTC_HN_AY_GUOBO:现在主要是在kdtree的基础上有了mtree或者mvptree,其实关键还是pivot的选择,以及度量空间中算法怎么减少距离计算;
    2. mandycool:mvp-tree,是利用三角形不等式来缩小搜索区域的,不过mvp-tree的目标稍有不同,查询的是到query点的距离小于某个值r的点;另外作者test的数据集只有20维,不知道上百维以后效果如何,而减少距离计算的一个思路是做embedding,通过不等式排除掉一部分点。

        更多内容请参见论文1:DIST ANCE-BASED INDEXING FOR HIGH-DIMENSIONAL METRIC SP ACES,作者:Tolga Bozkaya & Meral Ozsoyoglu,及论文2:基于度量空间高维索引结构VP-tree及MVP-tree的图像检索王志强,甘国辉,程起敏

        当然,如果你觉得上述论文还不够满足你胃口的话,这里有一大堆nearest neighbor algorithms相关的论文可供你看:http://scholar.google.com.hk/scholar?q=nearest+neighbor+algorithms&btnG=&hl=zh-CN&as_sdt=0&as_vis=1(其中,这篇可以看下Spill-Trees,An investigation of practical approximate nearest neighbor algorithms

    展开全文
  •  设有一页式存储管理系统,向用户提供的逻辑地址空间最大为16页,每页2048字节,内存总共有8个存储块,试问逻辑地址至少应为多少位?内存空间有多大?  答:2的4次方=16,所以页号占4位,页长为2048=2的11次方,...


          

       * 在分页存储管理方式中,程序经过页面划分后,页内地址相对于0编址。因此,分页系统中,每个逻辑地址都可用二(页号,页内位移即页内地址)表示。



       *一个32位的逻辑地址,可转化为如下方式:


        

        



       4095是2的12次方减一(根据框上的逻辑地址位数可以得到页号的编号及页内地址的相对地址范围)


           *物理地址同样用二元组(块号,块内地址)表示。

           

     逻辑地址转换过程:

         逻辑地址A,在分页在存储管理方式中,需要被转换成(页号,页内位移量) 二元组地址形式。 

    若页面大小为L,则转换过程为:   

          页号P=INT[A/L];页内位移量  W=A MOD L

       

      变换通常由系统中的某些硬件完成(MMU,内存管理单元)

         例:有逻辑地址为2170,页面大小为1KB

          P=INT[2170/1024]=2      W=2170MOD 1024=122

        (页面大小为1KB则页内地址为1K )

        设有一页式存储管理系统,向用户提供的逻辑地址空间最大为16页,每页2048字节,内存总共有8个存储块,试问逻辑地址至少应为多少位?内存空间有多大?


             答:2的4次方=16,所以页号占4位,页长为2048=2的11次方,所以页内地址占11位,逻辑地址15位
    存储块有8个,每个存储块对应2048B大小的页框,所以主存空间为16KB

            页内地址等于块内地址

    
    
    展开全文
  • Linux空间划分 & MMU

    千次阅读 2014-09-06 21:13:52
    Linux内核地址空间划分 ...32位的Linux系统中从0x00000000到0xFFFFFFFF整个4GB虚拟存储空间。  内核空间:内核空间表示运行在处理器最高级别的超级用户模式(supervisor mode)下的代码或数据,内核空间占
  • 本节学习聚类分析,聚类属于无监督学习,其中聚类的方法有很多种常见的有K-means、层次聚类(Hierarchical clustering)、谱聚类(Spectral Clustering)等,在这里,上来不会直接介绍这些理论,需要一些基础知识...
  • 一、外存分配方式 二、储空间管理
  • 基本分段存储管理方式

    千次阅读 2018-11-25 12:58:08
    一、分段系统的基本原理 1、程序通过分段(segmentation)划分为多个模块,每个段定义一组逻辑信息。如代码段(主程序段main,子程序段X)、数据段D、栈段S等。 2、每段有自己的名字(一般用段号做名),都从0编址,可...
  • 进程地址空间与虚拟存储空间的理解

    万次阅读 多人点赞 2009-10-17 22:33:00
    分页的基本方法是,将地址空间分成许多的页。每页的大小由 CPU 决定,然后由操作系统选择页的大小。目前 Inter 系列的 CPU 支持 4KB 或 4MB 的页大小,而 PC 上目前都选择使用 ...
  • 一直以来对手机设置中的RAM及内部存储空间不理解,做手机三年了别人问起来我都是稀里糊涂的,在加上今天老板让我将nand区域划分出一块作为手机内部存储使用,我彻底糊了,遂下决心搞懂了下面几个概念: 以下概念都...
  • 云计算云存储的一些基本概念

    万次阅读 多人点赞 2018-04-12 20:10:04
    我们在学习云计算和云存储之前,需要先了解一些很常见的基本概念,否则在学习过程中和选型时会比较晕。 云计算的三种服务模式:IaaS,PaaS和SaaS 云的分层 任何一个在互联网上提供其服务的公司都可以叫做云计算...
  • 存储管理方法详解

    千次阅读 2014-09-19 17:11:29
    其目的是充分利用内存空间,为多道程序并发执行提供存储基础,并尽可能地方便用户使用。 3.1 存储管理的目的   采用多道程序设计技术,就要在内存中同时存放多道程序,这就要求存储管理解决以下四个重要...
  • 数据库存储方法

    千次阅读 2017-08-30 11:14:29
    在数据库中,有两种数据存放方法: 1、堆:数据按照向后插入的方法,一直堆积在文件末尾,使用...性能得到部分提升),由于没有填充因子,在相同压缩算法下,空间能得到很大的节省,堆表很适合于顺序范围访问,如数据
  • 基本分页存储管理方式

    万次阅读 多人点赞 2018-07-26 20:16:41
    连续分配存储管理方式产生的问题 在分区存储管理中,要求把进程放在一个连续的存储区中,因而会产生许多碎片。 碎片问题的解决方法 (1)拼接/紧凑技术----代价较高。...段页式存储管理:离散分配的基本单位是...
  • java虚拟机在执行java程序的过程中会把它所管理的内存划分成若干个不同的数据区域。这些区域各有用途,以及创建和销毁的时间。有的区域随着虚拟机的进程的启动而存在,有的则依赖用户线程的启动和结束而建立和销毁。...
  • 3.1.4.1 基本分页存储管理方式

    千次阅读 2016-07-13 23:58:02
    分页存储管理方式中,又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。 1、基本分页存储管理方式 固定分区会产生内部碎片,动态分区会产生外部碎片,这...
  • 本篇介绍Java数据类型的划分及8种基本数据类型
  • 我们在上篇文章已经对比了不同的存储系统之间的区别,本章开始逐步深入记录Ceph的学习和运用。 开源分布式存储系统的对比 Ceph简介 Ceph是一个分布式存储系统,提供对象,块和文件存储,是一个免费开源软件的存储...
  • 操作系统基本分段存储管理方式

    千次阅读 2014-05-03 10:11:21
    操作系统基本分段存储管理方式 引入分段存储管理方式的目的:满足程序员在编程和使用上多方面的要求。这种存储管理方式已经成为当今所有存储管理方式的基础。 1、分段存储管理方式的引入 主要满足用户和程序员以下...
  • 存储基本概念(lun,volume,HBA,DAS,NAS,SAN,iSCSI,IPSAN)

    万次阅读 多人点赞 2015-05-05 19:07:46
    磁盘阵列上的硬盘组成RAID组后,通常连接磁盘阵列的服务器并不能直接访问RAID组,而是要再划分为逻辑单元才能分配给服务器。这是因为SCSI总线上可挂接的设备数量是有限的,一般为8个或者16个,我们可以用Target ID...
  • 操作系统基本分页存储管理方式

    千次阅读 2014-05-01 22:54:03
    操作系统基本分页存储管理方式 连续分配内存方式会形成许多“碎片”,通过紧凑的方式将碎片拼接成一块大的空间,但是拼接过程系统开销太大。如果允许将一个进程直接分散地装入到许多不相邻的分区中,那么就不需要再...
  • 操作系统中存储管理的基本原理

    千次阅读 2014-09-03 09:31:13
    存储管理的基本原理 内存管理方法 内存管理主要包括内存分配和回收、地址变换、内存扩充、内存共享和保护等功能。 下面主要介绍连续分配存储管理、覆盖与交换技术以及页式与段式存储管理等基本概念和原理。...
  • 空间划分及可见性算法

    千次阅读 2015-03-31 15:30:50
    对每个物体转换到世界坐标,然后进行视椎体剔除,其次是背面消隐,最总通过空间剪裁和光栅化期间的图像空间裁剪得到最终的要绘制的图像。 在场景很简单,物体很少的情况,上述方法是可行的。但考虑到现代游戏的...
  • Hbase列族数据库(基本存储结构)

    千次阅读 2017-05-30 12:55:54
    •表:HBase采用表来组织数据,表由行和列组成,列划分为若干个列族 •行:每个HBase表都由若干行组成,每个行由行键(row key)来标识。 •列族:一个HBase表被分组成许多“列族”(Column Family)的集合,...
  • 基本属性:图像亮度,对比度,色彩饱和度,清晰度(锐度) 色阶:曝光、高光、阴影 颜色:色温、色调 . 1、图像亮度来源于:OpenCV改变图像或视频的亮度 改变亮度是在每个像素上的点操作。如果想提高亮度,必须
  • Java内存划分和分配

    千次阅读 2018-10-18 15:03:41
    综述 在这边文章中我们将了解一下Java的内存区域是怎么划分的以及每个区域的...首先通过一张图来看一下Java虚拟机是如何划分内存空间的。 程序计数器:是一块较小内存,可以看作是当前线程所执行的字节码的行号指示...
  • 基本分页和请求分页存储管理

    千次阅读 2013-11-20 21:34:02
    在存储器管理中,连续分配方式会形成许多“碎片”,虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间,但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻的分区中,则无须再进行“紧凑”。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 167,108
精华内容 66,843
关键字:

划分存储空间的基本方法